068.文本左右对齐

作者：沉默王二
发布时间：2022-12-27T10:53:23.039+0800

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

给定一个单词数组 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", 因为最后一行应为左对齐，而不是左右两端对齐。第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20

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

分析

如果本题只是一般的左对齐，那么就非常简单，只需要依次添加字符串和一个空格，然后等到剩余的格子数量不够填充了，再直接全部替换为空格即可，可惜本题是——左右两端对齐。

这使得我们不得不去考虑每个单词之间空格的划分问题。

我们先来考虑除去单词后剩余的空格数量。

如果这一行一共能放下n个单词，那么就会有n-1个空隙，而我们所要做的，就是把剩余的空格尽量均匀地分配到这n-1个空隙当中，如果不能均分，则要让靠左间隙的空格数量大于等于靠右的空格数量。

除此之外，还有一些情况需要我们左对齐：

最后一行
该行只有一个单词

这两种情况下，我们需要左对齐——即”单词+空格+单词+……+单词+空格“的方式对齐即可。

说起来简单，做起来难，我们在均分空隙的时候，仍然有很多的细节需要考虑。大家可以结合代码去加深理解。

class Solution {

List res = new ArrayList<>(); List temp = new ArrayList<>(); for(int i = 0;i < words.length;){ temp.clear(); temp.add(words[i]); int len = words[i].length(); i++; while(i < words.length && len + 1 + words[i].length() <= maxWidth){ len += 1 + words[i].length(); temp.add(words[i]); i++; } if(i == words.length){ StringBuilder add = new StringBuilder(); for (String s : temp) { add.append(s).append(" "); } add.deleteCharAt(add.length() - 1); for(int j = add.length();j < maxWidth;j++) add.append(" "); res.add(add.toString()); } else if(temp.size() == 1){ StringBuilder add = new StringBuilder(temp.get(0)); while(add.length() < maxWidth) add.append(" "); res.add(add.toString()); } else { //len是"单词+一个空格+单词+……+空格+单词"*单词数量 int wordLength = len - (temp.size() - 1); //最大长度-wordLength即为我们可以分配的空格总数 int spaceLength = maxWidth - wordLength; //进行分配时候的单位空格长度（下取整） int singleSpace = spaceLength / (temp.size() - 1); StringBuilder space = new StringBuilder(); space.append(" ".repeat(Math.max(0, singleSpace))); StringBuilder add = new StringBuilder(); int totSpaceLength = 0; for(int j = 0;j < temp.size();j++){ add.append(temp.get(j)); if(j == temp.size() - 1) break; add.append(space); totSpaceLength += singleSpace; if((temp.size() - j - 2) * singleSpace + totSpaceLength < spaceLength){ add.append(" "); totSpaceLength++; } } res.add(add.toString()); } } return res; }}

总结

本题是一道难度较高的字符串模拟，需要细心地观察和思考，一步步来，才能把这题的每个部分”解剖“完成。

力扣链接：https://leetcode.cn/problems/text-justification/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1200 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

题意

给定一个单词数组 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

示例 3:

输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20

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

分析

这使得我们不得不去考虑每个单词之间空格的划分问题。

我们先来考虑除去单词后剩余的空格数量。

除此之外，还有一些情况需要我们左对齐：

最后一行
该行只有一个单词

这两种情况下，我们需要左对齐——即”单词+空格+单词+……+单词+空格“的方式对齐即可。

说起来简单，做起来难，我们在均分空隙的时候，仍然有很多的细节需要考虑。大家可以结合代码去加深理解。

class Solution {

总结

本题是一道难度较高的字符串模拟，需要细心地观察和思考，一步步来，才能把这题的每个部分”解剖“完成。

力扣链接：https://leetcode.cn/problems/text-justification/

一步一个脚印

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

题意

给定一个单词数组 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

示例 3:

输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20

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

分析

这使得我们不得不去考虑每个单词之间空格的划分问题。

我们先来考虑除去单词后剩余的空格数量。

除此之外，还有一些情况需要我们左对齐：

最后一行
该行只有一个单词

这两种情况下，我们需要左对齐——即”单词+空格+单词+……+单词+空格“的方式对齐即可。

说起来简单，做起来难，我们在均分空隙的时候，仍然有很多的细节需要考虑。大家可以结合代码去加深理解。

class Solution {

总结

本题是一道难度较高的字符串模拟，需要细心地观察和思考，一步步来，才能把这题的每个部分”解剖“完成。

力扣链接：https://leetcode.cn/problems/text-justification/

一步一个脚印

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412