LeetCode 0068 - Text Justification
# Hints
- 模拟
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given an array of words and a width maxWidth
, format the text such that each line has exactly maxWidth
characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' '
when necessary so that each line has exactly maxWidth
characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
Note:
A word is defined as a character sequence consisting of non-space characters only.
Each word's length is guaranteed to be greater than and not exceed
maxWidth
.The input array
words
contains at least one word.
Example 1:
Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Example 2:
Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be",
because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.
Example 3:
Input:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
# 题意
如题目所述地实现文本格式的转换。
# 题解
按题目要求模拟即可。细节比较多。
细节问题:
- 分配空格时的细节,例如把 个空格分给 个位置,分配的结果应为 。
# AC代码
class Solution {
public:
vector<string> fullJustify(vector<string> & words, int maxWidth) {
// 分配单词到各行
vector<vector<string>> rows;
vector<string> row;
vector<int> len_of_rows;
int len_of_row = 0;
for (int i = 0; i < words.size(); i ++) {
// 进入下一行
if (row.size() + len_of_row + (words[i].length() + 1) > maxWidth + 1) {
assert(!row.empty());
rows.push_back(row);
len_of_rows.push_back(len_of_row);
row.clear();
len_of_row = 0;
}
// 加入当前行
row.push_back(words[i]);
len_of_row += words[i].length();
}
// 生成字符串
vector<string> res;
for (int i = 0; i < rows.size(); i ++) {
// 获取当前行
vector<string> & row = rows[i];
int len_of_row = len_of_rows[i];
// 单个单词的情况
if (row.size() == 1) {
string str = row[0] + string(maxWidth - row[0].length(), ' ');
res.push_back(str);
continue;
}
// 计算空格数
int cnt = (row.size() - 1);
int space_of_row = (maxWidth - len_of_row) / cnt;
int rem = (maxWidth - len_of_row) % cnt;
// 生成
string str;
for (int j = 0; j < row.size() - 1; j ++) {
str += row[j] + string(space_of_row + (rem > 0), ' ');
rem --;
}
str += row.back();
res.push_back(str);
}
// 生成字符串(最后一行)
string str;
for (int j = 0; j < row.size() - 1; j ++) {
str += row[j] + ' ';
}
str += row.back();
str += string(maxWidth - str.length(), ' ');
res.push_back(str);
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01