leet code 68. 文本左右对齐

leet code 68. 文本左右对齐

题目描述

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词

使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；

也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，

使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。

如果某一行单词间的空格不能均匀分配，

则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

示例 1:

输入:

words = ["This", "is", "an", "example", "of", "text", "justification."]

maxWidth = 16

输出:

示例 2:

输入:

words = ["What","must","be","acknowledgment","shall","be"]

maxWidth = 16

输出:

解释:

注意最后一行的格式应为 "shall be "

而不是 "shall be", 因为最后一行应为左对齐，而不是左右两端对齐。

第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:

words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]

maxWidth = 20

输出:

提示:

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] 由小写英文字母和符号组成
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth

题目解析

从简单的细节开始考虑.

• 每一行放置的单词数的总长度+空格的数量 要等于 maxWidth

• 已知 words[i].length <= maxWidth
• 那么每一行最少要放一个单词。
• 如果放置两个单词，那么至少需要一个空格作为间隔，总长度要 小于等于 maxWidth
• 即， 最小需要的空格数量 = 选中的单词数量 - 1

• 那么确定好选择的单词数量之后就可以进行拼接分配了

• 每拼接完成一个结果，放入到结果集中

• 关键点分为两部分，选择单词 + 拼接结果

• 额外的：最后一行需要特别处理

注释版code

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        // 单词数组的长度.
        int n = words.length;
        List<String> ans = new ArrayList<>();

        int start = 0;
        while(start < n) {
            // 记录当前选取单词加空格需要的总长度.
            int localLen = 0;
            int t = start;
            while(t < n) {
                // 这个时候加上了一个单词的长度.
                localLen += words[t].length();

                if(localLen > maxWidth) {
                    // 超过了 maxWidth，那么当前单词要舍去
                    localLen -= words[t].length();
                    // 尾巴空格也舍去.
                    localLen--;
                    t--;
                    break;
                }

                // 总长度等于 maxWidth 的情况，直接退出循环.
                if(localLen == maxWidth) {
                    break;
                }

                // 每一个单词后面追加一个空格.
                localLen += 1;
                t++;
            }
            // 拼接组合结果集.
            combinationWords(words, ans, start, t == n?t - 1:t, localLen, maxWidth);
            start = t + 1;
        }

        // 单独处理最后一行.
        String lastLine = ans.get(ans.size() - 1);
        ans.remove(ans.size() - 1);

        String[] arr = lastLine.split(" ");
        int len = 0;
        StringBuilder last = new StringBuilder();
        for(String w : arr) {
            if("".equals(w)) {
                continue;
            }
            // 追加单词.
            last.append(w.replace(" ", ""));
            // 记录长度.
            len += w.length();
            if(len == maxWidth) {
                break;
            }
            // 追加空格.
            last.append(" ");
            // 记录长度.
            len += 1;
            if(len == maxWidth) {
                break;
            }
        }

        // 追加空格，如果有
        while(maxWidth - len > 0) {
            last.append(" ");
            len++;
        }
        ans.add(last.toString());

        return ans;
    }

    private void combinationWords(String[] words, List<String> ans, int start, int end, int len,int maxWidth) {
        StringBuilder builder = new StringBuilder();
        // 首先计算一共需要拼接多少个单词：wordNum
        int wordNum = end - start + 1;

        // 这个时候计算一下需要额外补充的空格数量.
        // len 表示单词+空格 平均分的长度.
        int replenishSpaceNum = maxWidth - len;

        // 额外需要补充的空格需要均匀分配到单词间隙之间.
        // 间隙数量.
        int gapNum = end - start;

        // 剩余的间隙数量--如果多余的空格是否能够平均分.
        int leftGapNum = 0;
        // 每一个间隙需要补充的空格数量.
        int avgGapNum = 0;
        if(gapNum == 0) {
            // 没有间隙，那么直接把剩余空格数量全部补充到末尾.
            avgGapNum = replenishSpaceNum;
        } else {
            avgGapNum = replenishSpaceNum / gapNum;
            leftGapNum = replenishSpaceNum % gapNum;
        }

        if(start == end) {
            // 仅仅有一个单词的情况.
            builder.append(words[start]);
            // 补充空格
            while(avgGapNum > 0) {
                builder.append(" ");
                avgGapNum--;
            }
            ans.add(builder.toString());
            return;
        }

        if(start + 1 == end) {
            // 仅仅两个单词的情况.
            builder.append(words[start]);
            // 补充空格 +1表示默认有一个空格了.
            while(avgGapNum + 1 > 0) {
                builder.append(" ");
                avgGapNum--;
            }
            builder.append(words[end]);
            ans.add(builder.toString());
            return;
        }

        // 开始拼接结果集合
        for(int i = start;i <= end;i++) {
            builder.append(words[i]);
            if(i <= end - 1) {
                // 需要补充的 空格 总数量.
                int needSpaceNum = avgGapNum + 1;
                // 最后剩余的空格优先分配.
                if(leftGapNum > 0) {
                    needSpaceNum++;
                    leftGapNum--;
                }
                while(needSpaceNum > 0) {
                    builder.append(" ");
                    needSpaceNum--;
                }
            }
        }
        ans.add(builder.toString());
    }
}

没看提示，没看答案，全独立完成困难程度题目，继续加油