LeetCode: Text Justification 解题报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode: Text Justification 解题报告，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5937字，纯文字阅读大概需要9分钟。
内容图文
Text Justification
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:
[
"This is an",
"example of text",
"justification. "
]
Note: Each word is guaranteed not to exceed L in length.
SOLUTION 1:
递归解答：
每一次只处理一行，其它行交给下一级递归来处理。
思路是：
1. 先贪心法取得我们这一行可以放多少单词。
2. 在每个单词后面计算空格1个，但最后一个的要加回来。因为最后一个单词不需要加空格在右边。
3. 余下的空格数，平均分配给所有的interval。
4. 如果不能取整，多出的从左到右分配给那些interval。
5. 如果是1个单词，或是最后一行，在最后补空格。
其实整个题目不算难。但很繁杂，起码提交了8，9次才算过。
1
public
class
Solution {
2
public List<String> fullJustify(String[] words, int L) {
3 List<String> ret = new ArrayList<String>();
4 5if (words == null) {
6return ret;
7 }
8 9 rec(words, L, 0, ret);
10return ret;
11 }
1213publicstaticvoid rec(String[] words, int L, int index, List<String> list) {
14int len = words.length;
15if (index >= len) {
16return;
17 }
1819int LenTmp = L;
2021int end = index;
22for (int i = index; i < len && words[i].length() <= L; i++) {
23 L -= words[i].length();
2425// the space follow the word.26 L--;
27 end = i;
28 }
2930// 最后一个空格收回31 L++;
3233// Count how many words do we have.34int num = end - index + 1;
3536int extraSpace = 0;
37int firstExtra = 0;
3839// 单词数大于1，才需要分配，否则所有的空格加到最后即可40if (num > 1) {
41 extraSpace = L / (num - 1);
42// 首单词后多跟的空格43 firstExtra = L % (num - 1);
44 }
4546 StringBuilder sb = new StringBuilder();
47for (int i = index; i <= end; i++) {
48 sb.append(words[i]);
4950// The space following every word.51if (i != end) {
52 sb.append(‘ ‘);
53 }
5455// 不是最后一行56if (end != len - 1) {
57// The first words.58if (firstExtra > 0) {
59 sb.append(‘ ‘);
60 firstExtra--;
61 }
6263// 最后一个单词后面不需要再加空格64if (i == end) {
65break;
66 }
6768// 每个单词后的额外空格69int cnt = extraSpace;
70while (cnt > 0) {
71 sb.append(‘ ‘);
72 cnt--;
73 }
74 }
75 }
7677// 最后一行的尾部的空格78int tailLen = LenTmp - sb.length();
79while (tailLen > 0) {
80 sb.append(‘ ‘);
81 tailLen--;
82 }
8384 list.add(sb.toString());
85 rec(words, LenTmp, end + 1, list);
86 }
87 }
SOLUTION 2:
其实之前的递归是一个尾递归，我们可以很容易地把尾递归转化为Iteration的解法。
以下是Iteration的解法：
思想是一致的。
1
//
SOLUTION 2: iteration.
2
public List<String> fullJustify(String[] words, int L) {
3 List<String> ret = new ArrayList<String>();
4if (words == null) {
5return ret;
6 }
7 8int len = words.length;
9int index = 0;
1011while (index < len) {
12int LenTmp = L;
1314int end = index;
15for (int i = index; i < len && words[i].length() <= LenTmp; i++) {
16 LenTmp -= words[i].length();
1718// the space follow the word.19 LenTmp--;
20 end = i;
21 }
2223// 最后一个空格收回24 LenTmp++;
2526// Count how many words do we have.27int num = end - index + 1;
2829int extraSpace = 0;
30int firstExtra = 0;
3132// 单词数大于1，才需要分配，否则所有的空格加到最后即可33if (num > 1) {
34 extraSpace = LenTmp / (num - 1);
35// 首单词后多跟的空格36 firstExtra = LenTmp % (num - 1);
37 }
3839 StringBuilder sb = new StringBuilder();
40for (int i = index; i <= end; i++) {
41 sb.append(words[i]);
4243// The space following every word.44if (i != end) {
45 sb.append(‘ ‘);
46 }
4748// 不是最后一行49if (end != len - 1) {
50// The first words.51if (firstExtra > 0) {
52 sb.append(‘ ‘);
53 firstExtra--;
54 }
5556// 最后一个单词后面不需要再加空格57if (i == end) {
58break;
59 }
6061// 每个单词后的额外空格62int cnt = extraSpace;
63while (cnt > 0) {
64 sb.append(‘ ‘);
65 cnt--;
66 }
67 }
68 }
6970// 最后一行的尾部的空格71int tailLen = L - sb.length();
72while (tailLen > 0) {
73 sb.append(‘ ‘);
74 tailLen--;
75 }
7677 ret.add(sb.toString());
78 index = end + 1;
79 }
8081return ret;
82 }
SOLUTION 3:
参考http://www.ninechapter.com/solutions/text-justification/
在solution2的基础上进行了一些简化，把append word的函数独立出来，解答如下，更加简洁：
1
//
SOLUTION 3: iteration2
2
public List<String> fullJustify(String[] words, int L) {
3 List<String> ret = new ArrayList<String>();
4if (words == null) {
5return ret;
6 }
7 8int len = words.length;
9int index = 0;
1011while (index < len) {
12int LenTmp = L;
1314int end = index;
15for (int i = index; i < len && words[i].length() <= LenTmp; i++) {
16 LenTmp -= words[i].length();
1718// the space follow the word.19 LenTmp--;
20 end = i;
21 }
2223// 最后一个空格收回24 LenTmp++;
2526// Count how many words do we have.27int num = end - index + 1;
2829int extraSpace = 0;
30int firstExtra = 0;
3132// 单词数大于1，才需要分配，否则所有的空格加到最后即可33if (num > 1) {
34 extraSpace = LenTmp / (num - 1);
35// 首单词后多跟的空格36 firstExtra = LenTmp % (num - 1);
37 }
3839 StringBuilder sb = new StringBuilder();
40for (int i = index; i <= end; i++) {
41 sb.append(words[i]);
4243int cnt = 0;
4445if (i == end) {
46break;
47 }
4849// 不是最后一行50if (end != len - 1) {
51// The first words.52if (firstExtra > 0) {
53 cnt++;
54 firstExtra--;
55 }
5657// 最后一个单词后面不需要再加空格
58// 每个单词后的额外空格59 cnt += extraSpace;
60 }
6162// 1: 每个单词后本来要加的空格63 appendSpace(sb, cnt + 1);
64 }
6566// 最后一行的尾部的空格，或者是只有一个单词的情况67 appendSpace(sb, L - sb.length());
6869 ret.add(sb.toString());
70 index = end + 1;
71 }
7273return ret;
74 }
7576publicvoid appendSpace(StringBuilder sb, int cnt) {
77while (cnt > 0) {
78 sb.append(‘ ‘);
79 cnt--;
80 }
81 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/FullJustify.java
原文：http://www.cnblogs.com/yuzhangcmu/p/4127290.html
内容总结
以上是互联网集市为您收集整理的LeetCode: Text Justification 解题报告全部内容，希望文章能够帮你解决LeetCode: Text Justification 解题报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。