给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ‘ ‘ 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
说明:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0，小于等于 maxWidth。
- 输入单词数组 words 至少包含一个单词。
示例:
输入:
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 "
]
代码
- 贪婪思想
- 从开始遍历，一行一行的生成
- 看清楚规则，计算好单词之间的空格数量
class Solution {
private String getBlanks(int length) {
StringBuilder t = new StringBuilder();
for (int i = 0;i < length;i++){
t.append(" ");
}
return t.toString();
}
private String adjust(List<String> temp,int count,int maxWidth){
if (temp.size() == 1) {
return temp.get(0)+getBlanks(maxWidth-temp.get(0).length());
}else {
// 需要进行空格填充
StringBuilder t = new StringBuilder();
int rest = maxWidth - count;// 剩余空格数
for (int j = 0;j < temp.size() ;j++) {
t.append(temp.get(j));
// rest/temp.size() 单词之间至少有几个空格 + 1是之前已经计算了一个空格
for (int k = 0;k < rest/(temp.size() - 1) + 1;k++) {
t.append(" ");
}
// 最左边的单词可能多一个空格，前多少个单词可以多呢？
if (j < rest % (temp.size() - 1) - 1) {
t.append(" ");
}
}
return t.toString().trim();
}
}
public List<String> fullJustify(String[] words, int maxWidth) {
// 贪婪算法，走一步看一步，调整
List<String> res = new ArrayList<>();
List<String> temp = new ArrayList<>();
int count = 0;
for (int i = 0;i < words.length;i++) {
// 加上一个单词和一个空格，判断是否超过限制长度
if (words[i].length() + count + 1 < maxWidth){
count += (1 + words[i].length());
temp.add(words[i]);
}else if(words[i].length() + count + 1 >= maxWidth){
if (words[i].length() + count == maxWidth) {// 恰好只隔一个空格
temp.add(words[i]);
StringBuilder t = new StringBuilder();
for (String wd : temp) {
t.append(" ").append(wd);
}
res.add(t.toString().trim());
temp.clear();
count = 0;
} else {
// 要对最后一行进行特殊处理
res.add(adjust(temp,count - 1,maxWidth));
temp.clear();
temp.add(words[i]);
count = words[i].length();
}
}
// 最后一行单词
if (i == words.length - 1 && count < maxWidth) {
if (temp.size() == 1){
res.add(temp.get(0)+getBlanks(maxWidth-temp.get(0).length()));
}else {
StringBuilder t = new StringBuilder();
t.append(temp.get(0));
count = temp.get(0).length();
for (int i = 1;i < temp.size();i++) {
t.append(" "+temp.get(i));
count = temp.get(i).length() + 1;
}
t.append(getBlanks(maxWidth - count));
res.add(t.toString())
}
}
}
return res;
}
}
- AC 代码
// 来源 https://leetcode.wang/leetCode-68-Text-Justification.html
class Solution {
private String getBlanks(int length) {
StringBuilder t = new StringBuilder();
for (int i = 0;i < length;i++){
t.append(" ");
}
return t.toString();
}
public List<String> fullJustify(String[] words, int maxWidth) {
// 贪婪算法，走一步看一步，调整
List<String> res = new ArrayList<>();
int start = 0,end = 0;
int count = 0;
for (int i = 0;i < words.length;) {
if (count == 0 && count + words[i].length() <= maxWidth
|| count > 0 && count + 1 + words[i].length() <= maxWidth) {
end++;// 更新end
if (count == 0) {
count += words[i].length();
}else {
count += words[i].length() + 1;
}
i++;
} else {
int sub = maxWidth - count + (end-start) - 1;
if (end - start == 1) {
String blank = getBlanks(sub);
res.add(words[start] + blank);
} else {
StringBuilder t = new StringBuilder();
t.append(words[start]);
int avgBlanks = sub / ((end - start) - 1);
int missing = sub - avgBlanks * ((end - start) - 1);
String blank = getBlanks(avgBlanks + 1);
int k = 1;
for (int j = 0;j < missing;j++) {
t.append(blank + words[start + k]);
k++;
}
blank = getBlanks(avgBlanks);
for (;k < (end - start);k++){
t.append(blank + words[start+k]);
}
res.add(t.toString());
}
start = end;
count = 0;
}
}
StringBuilder t = new StringBuilder();
t.append(words[start]);
for (int i = 1;i < (end - start);i++){
t.append(" " + words[start + i]);
}
t.append(getBlanks(maxWidth - count));
res.add(t.toString());
return res;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
