Hard LinkedIn Tag
这个题第一次做的时候确实是完全懂的，但是拿来再自己做还是挺多细节不知道怎么处理的。而且这种题本身就是很龟毛的那种题，自己想有点overwhelming感觉一大波细节向你袭来。
这道题注意几个地方吧：
大框架用while循环移动start index(此行开始的word index), 每次找到这一行能写的所有词最后一个词的index 后面那个index last(方便内部while 循环break出来）
先加words[index], 然后根据两类情况处理后面的单词安排。
一种情况是左对齐，当此行是最后一行或者此行只有一个单词，我们就左对齐。意思就是单词之间正常间隔一个space, 不再添加额外的space，然后写完了单词之后全是空格.
一种情况是中间对齐。这种情况就要计算gap数，每个gap应该平摊多少个extra spaces, 以及如何分配平均分配后剩余下来的spaces.
计算numOfGaps很简单，只需要计算改行总的单词然后减一即可。注意我们对于两种大情况，都是先把正常间隔的那一个space是考虑了进去的。所以第一种情况，我们直接遍历index后面的所有改行单词，先加一个空格，再加单词。 加完之后把改行还不到maxWidth剩下的用space填满。
第二种情况，我们要计算除开那个正常情况下间隔的一个空格之外，每个单词之间还要平摊几个:spacesPerGap = (maxWidth - curtLen) / numOfGaps;如果还有剩下的地方没填满，我们还要从左到右拿空格去填，所以我们也要计算remainSpaces = (maxWidth - curtLen) % numOfGaps; 然后我们遍历index之后的所有单词，每次都先把空格给填好了，先是把spacesPerGap填好，然后看看如果还剩下remianSpaces就填一个。再填单词。这样最后一次循环结束后index跳到last继续看下一个单词。
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
if (words == null || words.length == 0){
return res;
}
int index = 0;
while (index < words.length){
int curtLen = words[index].length();
int last = index + 1;
while (last < words.length){
if (curtLen + 1 + words[last].length() > maxWidth){
break;
}
curtLen += 1 + words[last].length();
last++;
}
StringBuilder line = new StringBuilder();
line.append(words[index]);
int numOfGaps = last - 1 - index;
//left justify
if (last == words.length || numOfGaps == 0){
for (int i = index + 1; i < last; i++){
line.append(" ");
line.append(words[i]);
}
for (int i = line.length(); i < maxWidth; i++){
line.append(" ");
}
} else {
//middle justify
//first distribute spaces evenly
//then from left to right assign spaces left
int spacePerGap = (maxWidth - curtLen) / numOfGaps;
int remainSpaces = (maxWidth - curtLen) % numOfGaps;
for (int i = index + 1; i < last; i++){
for (int k = 0; k < spacePerGap; k++){
line.append(" ");
}
if (remainSpaces > 0){
line.append(" ");
remainSpaces--;
}
line.append(" ");
line.append(words[i]);
}
}
res.add(line.toString());
index = last;
}
return res;
}
}
