本题虽说是个困难级别的题,但是如果看懂了给的样例,还是非常好实现的。
这道题其实能说的点不多,就是完全模拟
题目提到了很关键的一点:
[尽可能多地往每行中放置单词],为了满足每行多放,那么就让每行的单词之间仅有一个空格,看看能放置几个单词
第二个关键点:每行的能放置的单词确认完后,就要考虑空格如何分配。比如 [This is an],这三个单词,起初至少要保证单词有一个空格,那么这三个单词间就至少有两个空格,这两个空格作为我们 再分配 空格的基础条件。
maxWidth = 16, 16 - 8 = 8(考虑这三个单词本身的长度,最多可分配8个空格),8 / 2 = 4, 因此没两个单词之间可分配四个空格。
具体逻辑参见代码。
public List<String> fullJustify(String[] words, int maxWidth) {
int i = 0, len = words.length;
List<String> res = new ArrayList<>();
while(i < len) {
//一行中最少能放置一个单词
int left = i;//没行单词的起点
int curLen = words[i].length();
i++;
while(i < len) {
//每一行尽可能容纳多的单词,所以单词间的空格数至少是1
int l2 = words[i].length();
if(curLen + l2 + 1 > maxWidth)
break;
curLen += l2 + 1;
i++;
}
StringBuilder sb = new StringBuilder();
if(i == len) {
for(int j = left; j < i; j++) {
sb.append(words[j] +" ");
}
int l2 = sb.length();
sb.deleteCharAt(l2 - 1);
for(int j = sb.length(); j < maxWidth; j++) {
sb.append(" ");
}
res.add(sb.toString());
break;
}
//尝试为单词间分配空格
int all_words_len = 0;
for(int j = left; j < i; j++) {
all_words_len += words[j].length();
}
//最少需要几个空格
int low_space = i - left - 1;
int can_space = maxWidth - all_words_len;
int real_space = 0, b = 0;
//这个判断是考虑 如果最后一行只放一个单词的话
if(low_space != 0) {
real_space = can_space / low_space;
b = can_space % low_space;
}
for(int j = left; j < i; j++) {
if(sb.length() > 0) {
for(int k = 0; k < real_space; k++)
sb.append(" ");
if(b != 0) {
sb.append(" ");
b--;
}
}
sb.append(words[j]);
}
for(int j = sb.length(); j < maxWidth; j++) {
sb.append(" ");
}
res.add(sb.toString());
}
return res;
}