題目描述：給定一個單詞數(shù)組和一個長度?maxWidth，重新排版單詞，使其成為每行恰好有?maxWidth?個字符，且左右兩端對齊的文本。
你應該使用“貪心算法”來放置給定的單詞；也就是說，盡可能多地往每行中放置單詞。必要時可用空格?' '?填充，使得每行恰好有 maxWidth?個字符。
要求盡可能均勻分配單詞間的空格數(shù)量。如果某一行單詞間的空格不能均勻分配，則左側(cè)放置的空格數(shù)要多于右側(cè)的空格數(shù)。
文本的最后一行應為左對齊，且單詞之間不插入額外的空格。
說明:
單詞是指由非空格字符組成的字符序列。
每個單詞的長度大于 0，小于等于?maxWidth。
輸入單詞數(shù)組 words?至少包含一個單詞。
示例:
輸入:
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;) {
? ? ? ? //判斷加入該單詞是否超過最長長度
? ? ? ? //分了兩種情況，一種情況是加入第一個單詞，不需要多加 1
? ? ? ? //已經(jīng)有單詞的話，再加入單詞，需要多加個空格，所以多加了 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);
? ? ? ? ? ? ? ? //如果除不盡，計算剩余空格數(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 個空白
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）
著作權歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權，非商業(yè)轉(zhuǎn)載請注明出處。
