24.文本左右对齐
题目
给定一个单词数组 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
思路
字符串大模拟，分情况讨论即可：
- 如果当前行只有一个单词，特殊处理为左对齐；
- 如果当前行为最后一行，特殊处理为左对齐，此时最后一行可能是只有一个单词，也可能是有多个单词；
- 其余为一般情况，分别计算「当前行单词总长度」、「当前行空格总长度」和「往下取整后的单位空格长度」，然后依次进行拼接。当空格无法均分时，每次往靠左的间隙多添加一个空格，直到剩余的空格能够被后面的间隙所均分。
class Solution {
fun fullJustify(words: Array<String>, maxWidth: Int): List<String> {
// 每个元素都是一行的数据
val result = ArrayList<String>()
val wordCount = words.size
var lineFirstIndex = 0
while (lineFirstIndex < wordCount) {
// ① 贪心：内层循环确定这一行放 [lineFirstIndex, lineEndIndex)
var lineEndIndex = lineFirstIndex
// 每行的长度，且每行都要重新清零
var currentLength = 0
// // 加上新单词长度
while (lineEndIndex < wordCount &&
currentLength + words[lineEndIndex].length +
(lineEndIndex - lineFirstIndex) <= maxWidth
) {
currentLength += words[lineEndIndex].length
lineEndIndex++
}
// 间隙数
val gaps = lineEndIndex - lineFirstIndex - 1
// 要填的空格总数
val lengthDiff = maxWidth - currentLength
// 每行拼到一起
val sb = StringBuilder()
if (lineEndIndex == wordCount || gaps == 0) {
// 最后一行或者这一行只有一个单词，需要左对齐：单词间一个空格，行末补满
// 注意最后一行有可能是多个单词
for (i in lineFirstIndex until lineEndIndex) {
sb.append(words[i])
if (i < lineEndIndex - 1) {
// 如果是多个单词就在每个单词间加一个空格
sb.append(' ')
}
}
// 把右边剩余的部分都加上空格
while (sb.length < maxWidth) {
sb.append(' ')
}
} else {
// 两端对齐
val space = lengthDiff / gaps
var left = lengthDiff % gaps
for (i in lineFirstIndex until lineEndIndex) {
sb.append(words[i])
if (i < lineEndIndex - 1) {
// 最后一个单词后不补
repeat(space) { sb.append(' ') }
if (left > 0) {
// 不够分的部分，从左往右每个单词间加一个空格
sb.append(' ');
left--
}
}
}
}
result.add(sb.toString())
lineFirstIndex = lineEndIndex
}
return result
}
}
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ans = new ArrayList<>();
int n = words.length;
List<String> list = new ArrayList<>();
// i 是当前行第一个单词的下标
for (int i = 0; i < n; ) {
// list 装载当前行的所有 word
list.clear();
list.add(words[i]);
int cur = words[i++].length();
while (i < n && cur + 1 + words[i].length() <= maxWidth) {
cur += 1 + words[i].length();
list.add(words[i++]);
}
// 当前行为最后一行，特殊处理为左对齐
if (i == n) {
StringBuilder sb = new StringBuilder(list.get(0));
for (int k = 1; k < list.size(); k++) {
sb.append(" ").append(list.get(k));
}
while (sb.length() < maxWidth) sb.append(" ");
ans.add(sb.toString());
break;
}
// 如果当前行只有一个 word，特殊处理为左对齐
int cnt = list.size();
if (cnt == 1) {
String str = list.get(0);
while (str.length() != maxWidth) str += " ";
ans.add(str);
continue;
}
/**
* 其余为一般情况
* wordWidth : 当前行单词总长度;
* spaceWidth : 当前行空格总长度;
* spaceItem : 往下取整后的单位空格长度
*/
int wordWidth = cur - (cnt - 1);
int spaceWidth = maxWidth - wordWidth;
int spaceItemWidth = spaceWidth / (cnt - 1);
String spaceItem = "";
for (int k = 0; k < spaceItemWidth; k++) spaceItem += " ";
StringBuilder sb = new StringBuilder();
for (int k = 0, sum = 0; k < cnt; k++) {
String item = list.get(k);
sb.append(item);
if (k == cnt - 1) break;
sb.append(spaceItem);
sum += spaceItemWidth;
// 剩余的间隙数量（可填入空格的次数）
int remain = cnt - k - 1 - 1;
// 剩余间隙数量 * 最小单位空格长度 + 当前空格长度 < 单词总长度，则在当前间隙多补充一个空格
if (remain * spaceItemWidth + sum < spaceWidth) {
sb.append(" ");
sum++;
}
}
ans.add(sb.toString());
}
return ans;
}
}
复杂度分析:
- 时间复杂度：会对 words 做线性扫描，最坏情况下每个 words[i] 独占一行，此时所有字符串的长度为 n∗maxWidth。复杂度为 O(n∗maxWidth)
-
空间复杂度：最坏情况下每个 words[i] 独占一行，复杂度为 O(n∗maxWidth)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!