脚本宝典收集整理的这篇文章主要介绍了LeetCode 0068 Text Justification,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
原题传送门
1、思路分析 按从左往右的顺序遍历words,逐word添加到当前行。 辅助函数, findRight 尽可能多地把word加入到当前行,返回最后一个加入到当前行的word的下标。 辅助函数, justify 构造结果中的一行,需要分情况讨论 case 1: 若只有1个word,则当前行就是这个word; case 2: 若是最后1行,则当前行所有word均由1个空格进行分隔; case 3: 其他情况,尽可能把空格平均到每个单词之间的间隙,若不能平均分,则优先把空格分配到左边。
2、代码实现
package Q0099.Q0068TextJustification;
import java.util.ArrayList;
import java.util.List;
/*
We start with left being the first word.
findRight: Then we greedily try to go as far right as possible until we fill our current line.
Then we justify one line at a time.
justify: In all case we pad the right side with spaces until we reach max width for the line;
1. If it's one word then it is easy, the result is just that word.
2. If it's the last line then the result is all words separated by a single space.
3. Otherwise we calculate the size of each space evenly and if there is a remainder we distribute an extra space
until it is gone.
*/
public class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
int left = 0;
List<String> result = new ArrayList<>();
while (left < words.length) {
int right = findRight(left, words, maxWidth);
result.add(justify(left, right, words, maxWidth));
left = right + 1;
}
return result;
}
private int findRight(int left, String[] words, int maxWidth) {
int right = left;
int sum = words[right++].length();
while (right < words.length && (sum + 1 + words[right].length()) <= maxWidth)
sum += 1 + words[right++].length();
return right - 1;
}
private String justify(int left, int right, String[] words, int maxWidth) {
if (right - left == 0) return padResult(words[left], maxWidth);
boolean isLastLine = right == words.length - 1;
int numSpace = right - left;
int totalSpace = maxWidth - wordsLength(left, right, words);
String space = isLastLine ? " " : blank(totalSpace / numSpace);
int remainder = isLastLine ? 0 : totalSpace % numSpace;
StringBuilder result = new StringBuilder();
for (int i = left; i <= right; i++)
result.append(words[i])
.append(space)
.append(remainder-- > 0 ? " " : "");
return padResult(result.toString().trim(), maxWidth);
}
private int wordsLength(int left, int right, String[] words) {
int wordsLength = 0;
for (int i = left; i <= right; i++) wordsLength += words[i].length();
return wordsLength;
}
private String padResult(String result, int maxWidth) {
return result + blank(maxWidth - result.length());
}
private String blank(int length) {
return new String(new char[length]).replace('', ' ');
}
}
3、复杂度分析 时间复杂度: O(m),其中 m是数组words中所有字符串的长度之和。 空间复杂度: O(m)
package Q0099.Q0068TextJustification;
import java.util.ArrayList;
import java.util.List;
// Runtime: 0 ms, faster than 100.00% of Java online submissions for Text Justification.
public class Solution1 {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> result = new ArrayList<>();
if (words.length == 0 || maxWidth == 0) {
result.add("");
return result;
}
for (int i = 0, w; i < words.length; i = w) {
int len = -1;
for (w = i; w < words.length && len + words[w].length() + 1 <= maxWidth; w++)
len += words[w].length() + 1;
int evenlyDistributedSpaces = 1;
int extraSpaces = 0;
int numOfGapsBwWords = w - i - 1;
if (w != i + 1 && w != words.length) {
evenlyDistributedSpaces = ((maxWidth - len) / numOfGapsBwWords) + 1;
extraSpaces = (maxWidth - len) % numOfGapsBwWords;
}
StringBuilder sb = new StringBuilder(words[i]);
for (int j = i + 1; j < w; j++) {
for (int s = 0; s < evenlyDistributedSpaces; s++)
sb.append(' ');
if (extraSpaces > 0) {
sb.append(' ');
extraSpaces--;
}
sb.append(words[j]);
}
int remaining = maxWidth - sb.length();
while (remaining > 0) {
sb.append(' ');
remaining--;
}
result.add(sb.toString());
}
return result;
}
}
以上是脚本宝典为你收集整理的LeetCode 0068 Text Justification全部内容,希望文章能够帮你解决LeetCode 0068 Text Justification所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。