欢迎访问LeetCode题解合集
题目描述
给定一个单词数组和一个长度 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 "
]
题解:
模拟题。
首先需要计算出每行能放几个单词,使用双指针即可,然后根据单词个数讨论:
-
若只有一个单词,左对齐,剩下的部分填充空格
-
若是最后一行,左对齐,单词之间隔一个空格,剩下部分用空格填充
-
否则的话,需要计算单词间需要隔多少个空格,然后填进去即可:
假设一行能填的单词范围是 [i...j]
,单词的长度为 word_len
,那么单词间隙数目为 gap = j - i
,需要填补的空格数目为 space = maxWidth - word_len
。
由于题目要求 如果某一行单词间的空格不能均匀分配,则左侧放置的空格数要多于右侧的空格数,分配空格的方式可以为:
d = space / gap
,求出每个间隙至少放几个空格r = space % gap
,求出均分后还剩下几个空格
将前 r
个间隙填充 d + 1
个空格,剩下的填 d
个空格即可。
时间复杂度:$O(n)$
额外空间复杂度:$O(n * maxWidth)$
class Solution {
public:
void addSpace(string& s, int k) {
while ( k-- ) s += ' ';
}
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> ret;
int n = words.size();
int word_len, line_len, space, gap;
string line;
int d, r;
for ( int i = 0, j; i < n; ) {
line_len = word_len = words[i].size();
for ( j = i + 1; j < n; ++j ) {
if ( line_len + 1 + words[j].size() > maxWidth ) break;
line_len += 1 + words[j].size();
word_len += words[j].size();
}
line = words[i];
space = maxWidth - word_len;
if ( j == n ) {
for ( ++i; i < j; ++i )
line += ' ' + words[i];
addSpace( line, maxWidth - line.size() );
} else if ( j == i + 1 ) i = j, addSpace( line, space );
else {
gap = j - i - 1;
d = space / gap;
r = space % gap;
for ( ++i; i < j; ++i, --r ) {
if ( r > 0 ) addSpace( line, d + 1);
else addSpace( line, d );
line += words[i];
}
}
ret.push_back( move(line) );
}
return ret;
}
};
/*
时间:0ms,击败:100.00%
内存:7.1MB,击败:78.48%
*/