文本左右对齐
难度:
标签:
题目描述
给定一个单词数组 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 <= 3001 <= words[i].length <= 20words[i]由小写英文字母和符号组成1 <= maxWidth <= 100words[i].length <= maxWidth
代码结果
运行时间: 15 ms, 内存: 16.0 MB
/*
* 思路：
* 使用Java Stream处理集合，通过流的方式进行分组，计算空格数并填充。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class TextJustificationStream {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> result = new ArrayList<>();
List<List<String>> lines = new ArrayList<>();
List<String> line = new ArrayList<>();
int currentWidth = 0;
for (String word : words) {
if (currentWidth + word.length() + line.size() > maxWidth) {
lines.add(line);
line = new ArrayList<>();
currentWidth = 0;
}
line.add(word);
currentWidth += word.length();
}
lines.add(line);
lines.stream().forEach(l -> {
if (l.size() == 1) {
result.add(l.get(0) + " ".repeat(maxWidth - l.get(0).length()));
} else if (lines.indexOf(l) == lines.size() - 1) {
result.add(String.join(" ", l) + " ".repeat(maxWidth - l.stream().mapToInt(String::length).sum() - l.size() + 1));
} else {
int totalSpaces = maxWidth - l.stream().mapToInt(String::length).sum();
int gaps = l.size() - 1;
result.add(IntStream.range(0, l.size()).mapToObj(i -> l.get(i) + " ".repeat(i < gaps ? totalSpaces / gaps + (i < totalSpaces % gaps ? 1 : 0) : 0)).collect(Collectors.joining()));
}
});
return result;
}
}
解释
方法:
该题解使用贪心算法的思路来解决文本左右对齐的问题。首先遍历单词数组，将连续的单词组成一行，直到该行的长度超过最大宽度 maxWidth。对于每一行（最后一行除外），计算出需要插入的空格数，然后将空格尽可能均匀地分配到单词之间。如果空格无法均匀分配，则左侧放置的空格数要多于右侧。最后一行按照左对齐的方式处理，单词之间只插入一个空格，行末填充剩余空格。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在计算剩余空格数时，为什么使用的是`maxWidth - sum([len(s) for s in words])`，这里是否考虑了单词间至少需要一个空格的需求？
▷🦆
在处理最后一行时，为什么要单独进行左对齐处理，这与其他行有什么根本的不同？
▷🦆
对于`extra = remain_length % cnt`这一计算，如果某行只有一个单词，会发生什么情况？程序是否有处理这种特殊情况？
▷🦆
在实现中，每次添加单词到`tmp`列表时，为何还需增加`cur += 1`，这里的1代表了什么？
▷