題目描述：給定一個(gè)單詞數(shù)組和一個(gè)長度?maxWidth，重新排版單詞净宵，使其成為每行恰好有?maxWidth?個(gè)字符敲才，且左右兩端對(duì)齊的文本裹纳。
你應(yīng)該使用“貪心算法”來放置給定的單詞；也就是說紧武，盡可能多地往每行中放置單詞剃氧。必要時(shí)可用空格?' '?填充，使得每行恰好有 maxWidth?個(gè)字符阻星。
要求盡可能均勻分配單詞間的空格數(shù)量朋鞍。如果某一行單詞間的空格不能均勻分配，則左側(cè)放置的空格數(shù)要多于右側(cè)的空格數(shù)妥箕。
文本的最后一行應(yīng)為左對(duì)齊滥酥，且單詞之間不插入額外的空格。
說明:
單詞是指由非空格字符組成的字符序列畦幢。
每個(gè)單詞的長度大于 0坎吻，小于等于?maxWidth。
輸入單詞數(shù)組 words?至少包含一個(gè)單詞宇葱。
示例:
輸入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
輸出:
[
? ?"This ? ?is ? ?an",
? ?"example ?of text",
? ?"justification. ?"
]
代碼：
public List<String> fullJustify2(String[] words, int maxWidth) {
? ? List<String> ans = new ArrayList<>();
? ? int currentLen = 0;
? ? int start = 0;
? ? int end = 0;
? ? for (int i = 0; i < words.length;) {
? ? ? ? //判斷加入該單詞是否超過最長長度
? ? ? ? //分了兩種情況瘦真，一種情況是加入第一個(gè)單詞，不需要多加 1
? ? ? ? //已經(jīng)有單詞的話黍瞧，再加入單詞诸尽，需要多加個(gè)空格，所以多加了 1
? ? ? ? if (currentLen == 0 && currentLen + words[i].length() <= maxWidth
? ? ? ? ? ? || currentLen > 0 && currentLen + 1 + words[i].length() <= maxWidth) {
? ? ? ? ? ? end++;
? ? ? ? ? ? if (currentLen == 0) {
? ? ? ? ? ? ? ? currentLen = currentLen + words[i].length();
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? currentLen = currentLen + 1 + words[i].length();
? ? ? ? ? ? }
? ? ? ? ? ? i++;
? ? ? ? } else {
? ? ? ? ? ? int sub = maxWidth - currentLen + (end - start) - 1;
? ? ? ? ? ? if (end - start == 1) {
? ? ? ? ? ? ? ? String blank = getStringBlank(sub);
? ? ? ? ? ? ? ? ans.add(words[start] + blank);
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? StringBuilder temp = new StringBuilder();
? ? ? ? ? ? ? ? temp.append(words[start]);
? ? ? ? ? ? ? ? int averageBlank = sub / ((end - start) - 1);
? ? ? ? ? ? ? ? //如果除不盡印颤，計(jì)算剩余空格數(shù)
? ? ? ? ? ? ? ? int missing = sub - averageBlank * ((end - start) - 1);
? ? ? ? ? ? ? ? String blank = getStringBlank(averageBlank + 1);
? ? ? ? ? ? ? ? int k = 1;
? ? ? ? ? ? ? ? for (int j = 0; j < missing; j++) {
? ? ? ? ? ? ? ? ? ? temp.append(blank + words[start+k]);
? ? ? ? ? ? ? ? ? ? k++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? blank = getStringBlank(averageBlank);
? ? ? ? ? ? ? ? for (; k <(end - start); k++) {
? ? ? ? ? ? ? ? ? ? temp.append(blank + words[start+k]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ans.add(temp.toString());
? ? ? ? ? ? }
? ? ? ? ? ? start = end;
? ? ? ? ? ? currentLen = 0;
? ? ? ? }
? ? }
? ? StringBuilder temp = new StringBuilder();
? ? temp.append(words[start]);
? ? for (int i = 1; i < (end - start); i++) {
? ? ? ? temp.append(" " + words[start+i]);
? ? }
? ? temp.append(getStringBlank(maxWidth - currentLen));
? ? ans.add(temp.toString());
? ? return ans;
}
//得到 n 個(gè)空白
private String getStringBlank(int n) {
? ? StringBuilder str = new StringBuilder();
? ? for (int i = 0; i < n; i++) {
? ? ? ? str.append(" ");
? ? }
? ? return str.toString();
}
作者：windliang
鏈接：https://leetcode-cn.com/problems/text-justification/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-1-5/
來源：力扣（LeetCode）
著作權(quán)歸作者所有您机。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處年局。
