68. Text Justification

description

给定长度L和一个字符串数组,使输出的每一行的长度固定为L,并尽可能多得放入字符串,每个字符串之间最少有一个空格,将空格均匀分布到字符串之间,如果不能均匀分布,将剩下的空格从左往右分布到字符串间
最后一行每个字符串之间空一个空格即可,最后用空格补齐
中间如果只能放一个字符,后面用空格补齐

Given an array of words and a length L, format the text such that each line has exactly L 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 L 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.

For example,
words: [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]
L: 16.
Return the formatted lines as:

1
2
3
4
5
[
"This is an",
"example of text",
"justification. "
]

Note: Each word is guaranteed not to exceed L in length.

思路

像这样的题目首先是将问题分解为多个小问题,然后一个一个解决
可以分为两个问题:

  1. 如果每个字符串之间最少一个空格,每行长度最大为L,那么字符串数组可以分为几行?
  2. 对第一步分好的行按照要求均匀分布空格

这样这道题做起来就很简单了,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
单词比maxWidth长度小
最后一行比较特殊,每个单词之间空一个空格即可,将空格全部放到后面
对最后一行的考虑,补充"#"
对其他行中如果只有一个单词的处理,后面补" "
提交错误:
"",2 : " "
*/
public static List<String> fullJustify(String[] words, int maxWidth) {
List<String> list=new ArrayList<>();
String temp=words[0];
for(int i=1;i<words.length;i++){
if(temp.length()+words[i].length()<maxWidth) temp+="#"+words[i];
else {
list.add(temp);
temp=words[i];
}
}
while (temp.length()<maxWidth)temp+="#";//最后一行补充#
list.add(temp);
for(int i=0;i<list.size();i++){
temp=list.get(i);
temp=i<list.size()-1?getJustif(temp,maxWidth):temp.replace("#"," ");
list.remove(i);
list.add(i,temp);
}
return list;
}
private static String getJustif(String temp, int maxWidth) {
String[] strs=temp.split("#");
if (strs.length==1){
while (temp.length()<maxWidth)temp+=" ";
return temp;
}
int spit=(maxWidth-(temp.length()-strs.length+1))/(strs.length-1);
int last=(maxWidth-(temp.length()-strs.length+1))%(strs.length-1);
int count;
temp=strs[0];
for(int i=1;i<strs.length;i++){
if(last-->0)temp+=" ";
count=spit;
while (count-->0)temp+=" ";
temp+=strs[i];
}
return temp;
}

如果觉得有帮助,给我打赏吧!