力扣面试经典150题（第二十四题）

问题

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

提示:

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

我的回答

var fullJustify = function (words, maxWidth) {let strList = []; // 当前行的单词列表let strWidth = 0; // 当前行单词的总长度const ans = []; // 结果数组let i = 0; // 单词索引while (i < words.length) {// 判断当前单词是否可以加入当前行if (words[i].length + strWidth + strList.length <= maxWidth) {strList.push(words[i]);strWidth += words[i].length;i++;} else {// 处理当前行（非最后一行）if (strList.length > 1) {let junSpace = (maxWidth - strWidth) / (strList.length - 1); // 平均空格数let yuSpace = (maxWidth - strWidth) % (strList.length - 1); // 剩余空格数for (let j = 0; j < strList.length - 1; j++) {if (yuSpace > 0) {strList[j] += ' '.repeat(junSpace + 1); // 左侧优先分配空格yuSpace--;} else {strList[j] += ' '.repeat(junSpace);}}} else {// 只有一个单词时，右侧填充空格strList[0] += ' '.repeat(maxWidth - strList[0].length);}// 将当前行加入结果数组ans.push(strList.join(''));// 重置当前行状态strList = [];strWidth = 0;}}// 处理最后一行for (let j = 0; j < strList.length - 1; j++) {strList[j] += ' '; // 单词间仅保留一个空格}let lastLine = strList.join('');lastLine += ' '.repeat(maxWidth - lastLine.length); // 末尾填充空格ans.push(lastLine);return ans;
};

解题

我的方法的解题思路如下：

• 逐行处理单词：

  • 使用 strList 存储当前行的单词，strWidth 记录当前行中单词的总长度。
  • 遍历单词数组，尝试将每个单词加入当前行。如果加入后超出 maxWidth，则停止并处理当前行。

• 处理非最后一行：

  • 如果当前行包含多个单词，计算需要填充的总空格数 (maxWidth - strWidth)，并将其均匀分配到单词间隙中。
  • 使用整除和取余操作分别计算平均空格数和剩余空格数，优先将剩余空格分配到左侧。
  • 如果当前行只有一个单词，则直接在单词右侧填充空格。

• 处理最后一行：

  • 单词间仅保留一个空格，末尾用空格填充至 maxWidth。

• 输出结果：

  • 将每一行的字符串加入结果数组 ans。

关键点在于：

• 贪心算法的应用：

  • 每次尝试将尽可能多的单词放入当前行，直到无法再放入为止。
  • 使用 strWidth 和 strList 跟踪当前行的状态。

• 空格分配逻辑：

  • 非最后一行：通过整除和取余操作，计算每个间隙的平均空格数和剩余空格数。
  • 最后一行：直接左对齐，单词间保留一个空格，末尾补足空格。

• 边界条件处理：

  • 只有一个单词的行：所有空格都放在单词右侧。
  • 最后一行：特殊处理，避免多余的空格分配。