OJ练习第91题——文本左右对齐网站首页 技术杂谈

OJ练习第91题——文本左右对齐

盖盖的博客 2023-06-28 09:19:01

简介OJ练习第91题——文本左右对齐

文本左右对齐

力扣链接：68. 文本左右对齐

题目描述

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

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

注意:

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

示例

示例 1:

输入: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
输出:
[
“This is an”,
“example of text”,
"justification. "
]
示例 2:

输入:words = [“What”,“must”,“be”,“acknowledgment”,“shall”,“be”], maxWidth = 16
输出:
[
“What must be”,
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 “shall be”,
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。

Java代码

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        // 当前子串的个数
        int wordCount = 0;
        // 当前子串的字符长度
        int subStrLen = 0;
        StringBuilder sb  = new StringBuilder();
        for (int i= 0; i<words.length; i++) {
            String word = words[i];
            subStrLen += word.length();
            // 当前元素长度和元素间隔长度总和不能大于等于maxWidth
            //wordCount - 1 即间隔数（每个间隔至少一个空格）
            if(subStrLen + wordCount - 1 >= maxWidth) {
                // 如果叠加完当前字符串长度后超出最大长度限制，
                //那么当前字符串只能延迟到下一个子串中，需要回退一位
                i--;
                // 剩余长度，用于填充空串
                int remainLen = maxWidth - (subStrLen - word.length() - sb.length());
                int fillGap = wordCount - 1;
                // 计算间隙需要填充的最少空格个数
                int fillLen = wordCount == 1 ? remainLen : remainLen / fillGap;
                // 计算余数，如果不为0，则余数的填充字符均匀+1
                int remainder = fillGap == 0 ? 0 : remainLen % fillGap;
                for (int j = wordCount-1; j >=0; j--) {
                    String word1 = words[i - j];
                    if(j == 0 && wordCount > 1) {
                        fillLen = maxWidth - sb.length() - word1.length();
                        fillBlank(sb, fillLen);
                        sb.append(word1);
                    } else {
                        sb.append(word1);
                        int curFillLen = fillLen;
                        // 空格填充不均匀时，多个的空白字符从最左边开始填充
                        if(remainder != 0) {
                            curFillLen += 1;
                            remainder--;
                        }
                        fillBlank(sb, curFillLen);
                    }
                }
                res.add(sb.toString());
                // 数据复位
                sb = new StringBuilder();
                wordCount = 0;
                subStrLen = 0;
            } else {
                // 最后一个子串时，保持左对齐
                if(i == words.length - 1) {
                    sb = new StringBuilder();
                    for (int j = wordCount; j>=0; j--) {
                        sb.append(words[i - j]).append(" ");
                    }
                    sb = new StringBuilder(sb.substring(0, sb.length() - 1));
                    fillBlank(sb, maxWidth - sb.length());
                    res.add(sb.toString());
                } else {
                    wordCount++;
                }
            }
        }
        return res;
    }

    private void fillBlank(StringBuilder sb, int fillLen) {
        for (int k = 0; k < fillLen; k++) {
            sb.append(" ");
        }
    }
}