a***e
发帖数: 413 | 1 我不知道这种情况怎么继续努力啦，只能看看别人的答案？我觉得自己的思路是对的啊，
。。。有人碰到类似情况吗？
Last executed input:
["My","momma","always","said,",""Life","was","like","a","box
","of","chocolates.","You","never","know","what","you're","gonna","get."],
12
Given an array of words and a length L, format the text such that each line
has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words
as you can in each line. Pad extra spaces ' ' when necessary so that each
line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If
the number of spaces on a line do not divide evenly between words, the empty
slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is
inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[
"This is an",
"example of text",
"justification. "
]
Note: Each word is guaranteed not to exceed L in length.
class Solution {
public:
vector fullJustify(vector &words, int L) {
int n = words.size();
vector res;
if (n == 0) return res;
string tmp = words[0];
int num = 0;//num of spaces in between words
int start = 0;
for (int i = 1; i
{
while (tmp.length() + words[i].length() + 1
{
tmp = tmp + ' ' + words[i];
num++;
i++;
}
if (i >= n) break;
//add empty space
if (tmp.length()
{
int morespace = L - tmp.length();
int perspace = num == 0 ? morespace : morespace / num;
int extraspace = num == 0 ? 0 : morespace%num;
tmp.insert(words[start].length(), perspace + extraspace, ' ');
int pos = words[start].length() + perspace + extraspace+1;
for (int j = start + 1; j
{
pos += words[j].length()+1;
tmp.insert(pos, perspace, ' ');
}
}
res.push_back(tmp);
tmp = words[i];
num = 0;
start = i;
}
res.push_back(tmp);
return res;
}
}; | h**d
发帖数: 630 | 2 只有一个单词的行/最后一行的空格数不对
必须右边填满空格 | a***e
发帖数: 413 | 3 多谢。又是题没看清就开写了。。。。。。。
If
the number of spaces on a line do not divide evenly between words, the
empty
slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space
is
inserted between words.
这种题如果面试碰到，把题理解清楚都要花好久吧。。。。。。。。。有人真的在面试
的时候碰到类似的吗？面试官拿张纸给你还是口头描述？Text Justification 这个东
西我都是第一次听说，当然word里面老用。 | h**d
发帖数: 630 | 4 真的有人面过 没做过只有祈祷不遇到了
right.
【在 a***e 的大作中提到】
: 多谢。又是题没看清就开写了。。。。。。。
: If
: the number of spaces on a line do not divide evenly between words, the
: empty
: slots on the left will be assigned more spaces than the slots on the right.
: For the last line of text, it should be left justified and no extra space
: is
: inserted between words.
: 这种题如果面试碰到，把题理解清楚都要花好久吧。。。。。。。。。有人真的在面试
: 的时候碰到类似的吗？面试官拿张纸给你还是口头描述？Text Justification 这个东
| z***y
发帖数: 73 | 5 大概有三个问题：
1.
while (tmp.length() + words[i].length() + 1
应该i
2.
int pos = words[start].length() + perspace + extraspace+1;
我理解空格应该是均摊，比如4个词有5个空格，应该是2 2 1， 而不是 3 1 1
3.
最后一行要特殊处理，尾部加空格即可。 | a***e
发帖数: 413 | 6 多谢，是1的问题，改了后马上变成wrong answer 了。。呵呵
2. 我没理解对 If the number of spaces on a line do not divide evenly between
words, the empty slots on the left will be assigned more spaces than the
slots on the right.
【在 z***y 的大作中提到】
: 大概有三个问题：
: 1.
: while (tmp.length() + words[i].length() + 1: 应该i: 2.
: int pos = words[start].length() + perspace + extraspace+1;
: 我理解空格应该是均摊，比如4个词有5个空格，应该是2 2 1， 而不是 3 1 1
: 3.
: 最后一行要特殊处理，尾部加空格即可。
| a***e
发帖数: 413 | 7 又改写了，还是通不过，有大侠能看出明显错误吗？好奇那些面试官对这类题怎么知道
到底写对没？
8 / 24 test cases passed.
多谢。
Input:
["Listen","to","many,","speak","to","a","few."], 6
Output:
["Listen","to ","many, ","speak ","to a","few. "]
Expected:
["Listen","to ","many, ","speak ","to a","few. "]
class Solution {
public:
vector fullJustify(vector &words, int L) {
int n = words.size();
vector res;
if (n == 0) return res;
string tmp = words[0];
int num = 0;//num of spaces in between words
int start = 0;
for (int i = 1; i
{
while (i
{
tmp = tmp + ' ' + words[i];
num++;
i++;
}
if (i >= n) break;
//add empty space
if (tmp.length()
{
int morespace = L - tmp.length();
int perspace = num == 0 ? morespace : morespace / num;
int extraspace = num == 0 ? 0 : morespace%num;
if (num==1) extraspace=0;
int pos =0;
int c=0;
for (int j = start; j
{
pos += words[j].length();
if (c
{
tmp.insert(pos, perspace+1, ' ');
pos+=perspace+1;
c++;
}
else
{
tmp.insert(pos, perspace, ' ');
}
}
}
res.push_back(tmp);
tmp = words[i];
num = 0;
start = i;
}
if (tmp.length()
{
int morespace = L - tmp.length();
int perspace = num == 0 ? morespace : morespace / num;
int extraspace = num == 0 ? 0 : morespace%num;
tmp.insert(words[start].length(), perspace + extraspace, ' ');
}
res.push_back(tmp);
return res;
}
}; | z***y
发帖数: 73 | 8 for (int j = start; j
{
pos += words[j].length();
if (c
{
tmp.insert(pos, perspace+1, ' ');
pos+=perspace+1;
c++;
}
else
{
tmp.insert(pos, perspace, ' ');
}
}
这一段，start是开始的下标，i-1是结束下标吧？每一次都会往当前word后面插入空格
，最后一次是不是往末尾多加了空格？
前面连接的时候已经加过一个空格，pos是不是改是+=word[j].length() + 1
else里面不需要更新pos？
if (tmp.length()
{
int morespace = L - tmp.length();
int perspace = num == 0 ? morespace : morespace / num;
int extraspace = num == 0 ? 0 : morespace%num;
tmp.insert(words[start].length(), perspace + extraspace, ' ');
}
最后一行处理只要往后面append L个空格吧？ |
|
