Hard LinkedIn Tag
這個(gè)題第一次做的時(shí)候確實(shí)是完全懂的夺欲，但是拿來(lái)再自己做還是挺多細(xì)節(jié)不知道怎么處理的嫂伞。而且這種題本身就是很龜毛的那種題涨岁，自己想有點(diǎn)overwhelming感覺(jué)一大波細(xì)節(jié)向你襲來(lái)仍翰。

這道題注意幾個(gè)地方吧：

• 大框架用while循環(huán)移動(dòng)start index(此行開(kāi)始的word index), 每次找到這一行能寫(xiě)的所有詞最后一個(gè)詞的index 后面那個(gè)index last(方便內(nèi)部while 循環(huán)break出來(lái)）

• 先加words[index], 然后根據(jù)兩類(lèi)情況處理后面的單詞安排憔鬼。

• 一種情況是左對(duì)齊龟劲，當(dāng)此行是最后一行或者此行只有一個(gè)單詞胃夏，我們就左對(duì)齊。意思就是單詞之間正常間隔一個(gè)space, 不再添加額外的space昌跌，然后寫(xiě)完了單詞之后全是空格.

• 一種情況是中間對(duì)齊仰禀。這種情況就要計(jì)算gap數(shù)，每個(gè)gap應(yīng)該平攤多少個(gè)extra spaces, 以及如何分配平均分配后剩余下來(lái)的spaces.

計(jì)算numOfGaps很簡(jiǎn)單蚕愤，只需要計(jì)算改行總的單詞然后減一即可答恶。注意我們對(duì)于兩種大情況，都是先把正常間隔的那一個(gè)space是考慮了進(jìn)去的萍诱。所以第一種情況悬嗓，我們直接遍歷index后面的所有改行單詞，先加一個(gè)空格裕坊，再加單詞包竹。 加完之后把改行還不到maxWidth剩下的用space填滿(mǎn)。

第二種情況籍凝，我們要計(jì)算除開(kāi)那個(gè)正常情況下間隔的一個(gè)空格之外周瞎，每個(gè)單詞之間還要平攤幾個(gè):spacesPerGap = (maxWidth - curtLen) / numOfGaps;如果還有剩下的地方?jīng)]填滿(mǎn)，我們還要從左到右拿空格去填饵蒂，所以我們也要計(jì)算remainSpaces = (maxWidth - curtLen) % numOfGaps; 然后我們遍歷index之后的所有單詞声诸，每次都先把空格給填好了，先是把spacesPerGap填好退盯，然后看看如果還剩下remianSpaces就填一個(gè)双絮。再填單詞。這樣最后一次循環(huán)結(jié)束后index跳到last繼續(xù)看下一個(gè)單詞得问。

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;
    }
}