w********s
发帖数: 1570 | 1 搞了一天才pass，老是time limit exceeded.............. |
j**********3
发帖数: 3211 | 2 是。我看了2天才找到适合我的答案。。。还没写呢。。 |
j**********3
发帖数: 3211 | 3 btw，我去年写的当时可以passs现在改版了pass不了了。。。 |
g*********e
发帖数: 14401 | |
w********s
发帖数: 1570 | 5 那题很简单，我一遍救过
【在 g*********e 的大作中提到】
: 感觉是text justification
|
t********e
发帖数: 1169 | |
w********s
发帖数: 1570 | 7 那题也很简单
【在 t********e 的大作中提到】
: constant space的分糖果题
|
q********c
发帖数: 1774 | 8 这题标准解法是DP呀，为毛leetcode说用greedy?
【在 g*********e 的大作中提到】
: 感觉是text justification
|
w********s
发帖数: 1570 | 9 text justification和dp有毛关系。
class Solution {
public:
string reorder(string& s, int L, int nWords)
{
int diff = L - s.length();
if (nWords == 1)
{
string r = s;
for (int i = 0; i < diff; ++i) r += ' ';
return r;
}
int each = diff / (nWords - 1);
int extra = diff % (nWords - 1);
string r;
int l = s.length();
for (int i = 0; i < l; ++i)
{
char ch = s[i];
if (ch == ' ')
{
for (int j = 0; j < each; ++j)
{
r += ' ';
}
if (extra > 0)
{
r += ' ';
--extra;
}
}
r += ch;
}
return r;
}
string extract(vector& words, int L, int from, int* to)
{
string s;
s += words[from];
int k = from + 1;
int nWords = 1;
bool last = false;
while (true)
{
if (k >= words.size()) {last = true; break;}
string append = " " + words[k];
if (s.length() + append.length() > L) break;
s += append;
++k;
++nWords;
}
(*to) = k;
if (!last)
return reorder(s, L, nWords);
int diff = L - s.length();
for (int i = 0; i < diff; ++i)
s += ' ';
return s;
}
vector fullJustify(vector &words, int L) {
int to = 0;
int s = words.size();
int from = 0;
vector result;
while (to < s)
{
string str = extract(words, L, from, &to);
result.push_back(str);
from = to;
}
return result;
}
};
【在 q********c 的大作中提到】
: 这题标准解法是DP呀，为毛leetcode说用greedy?
|
q********c
发帖数: 1774 | 10 呵呵，greedy并不能保证最优解，会导致有的行字与字之间空格太大，不过如果题目这
样要求的话，我就不深究了。
【在 w********s 的大作中提到】
: text justification和dp有毛关系。
: class Solution {
: public:
: string reorder(string& s, int L, int nWords)
: {
: int diff = L - s.length();
: if (nWords == 1)
: {
: string r = s;
: for (int i = 0; i < diff; ++i) r += ' ';
|
|
|
j**********3
发帖数: 3211 | 11 啊？可否丢给我个link我看看，我没用dp也没用greedy。。。
让俺学学。。
【在 q********c 的大作中提到】
: 这题标准解法是DP呀，为毛leetcode说用greedy?
|
w********s
发帖数: 1570 | 12 他把所有不叫dp的方法都叫greedy
【在 j**********3 的大作中提到】
: 啊？可否丢给我个link我看看，我没用dp也没用greedy。。。
: 让俺学学。。
|
q********c
发帖数: 1774 | 13 呵呵，看来你是真不知道。给你一个视频：
http://ocw.mit.edu/courses/electrical-engineering-and-computer-
【在 w********s 的大作中提到】
: 他把所有不叫dp的方法都叫greedy
|
j**********3
发帖数: 3211 | 14 那个题dp咋做啊？？
【在 w********s 的大作中提到】
: 他把所有不叫dp的方法都叫greedy
|
y*****e
发帖数: 712 | 15 这题太恶心了，lc最恶心没商量， 有人能告诉我这题真的被面过吗？ |
r*******e
发帖数: 971 | |
y*****e
发帖数: 712 | 17 http://blog.csdn.net/whuwangyi/article/details/21611433
这是你给出的解法吗？ 我碰巧在网上看到这个，还看懂了，如果是的话非常感谢。
总之这题给我造成了严重的心理伤痕，如果小伙伴看自己不爽，就做这个题好了，不会
让你失望的。。
【在 r*******e 的大作中提到】
: 我给出了两种解法，可以参考一下。
|
l****o
发帖数: 315 | 18 我被面过，也许我就长着一张让面试官出难题的脸。
【在 y*****e 的大作中提到】
: 这题太恶心了，lc最恶心没商量， 有人能告诉我这题真的被面过吗？
|
r*******e
发帖数: 971 | 19 不好意思，居然没有给链接……
https://oj.leetcode.com/discuss/9523/share-two-similar-java-solution-that-
accpted-by-oj
这是我写的。然后你链接的算法对，就是写得不太规范，至少有好几处可以明显改进的。
希望有用。
【在 y*****e 的大作中提到】
: http://blog.csdn.net/whuwangyi/article/details/21611433
: 这是你给出的解法吗？ 我碰巧在网上看到这个，还看懂了，如果是的话非常感谢。
: 总之这题给我造成了严重的心理伤痕，如果小伙伴看自己不爽，就做这个题好了，不会
: 让你失望的。。
|
j*****s
发帖数: 32 | 20 我觉得edge case越多的题越烦，比如Median of Two Sorted Arrays，搞一次要死好多
脑细胞。 |
