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.
Corner Cases:
- A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.
-----------------4th pass---------------------------------
思路更第三遍完全一样。
public class Solution {
public List<String> fullJustify(String[] words, int L) {
List<String> list = new LinkedList<String>();
for(int start =0;start< words.length; ){
int curWordsLength = words[start].length();
int end = start; // j would be the last one within L
while(end+1<words.length && curWordsLength + words[end+1].length()+(end+1-start) <= L){
curWordsLength += words[end+1].length();
end++;
}
StringBuffer buf = new StringBuffer();
if(end == words.length-1){// no padding
for(int k = start;k<end;k++)
buf.append(words[k] + " ");
buf.append(words[end]);
for(int t = curWordsLength+(end-start);t<L;t++)
buf.append(" ");
}else{
for(int t =0;t<L- curWordsLength;t++)
words[start+ (start==end?0:t%(end-start))]+= " ";
for(int k = start;k<=end;k++)
buf.append(words[k]);
}
start=end+1;
list.add(buf.toString());
}
return list;
}
}
Mistakes:
1: line 15, 一开始没加， 反而在line13的k=start , k<=end 了。 这样明显是不对的。
2： 当有 % 运算是， 要先 检查 if divided by zero
----------------------------------------1st pass -----------------------------
public class Solution {
public ArrayList<String> fullJustify(String[] words, int L) {
// just the simple straightforward idea
ArrayList<String> al = new ArrayList<String>();
if(words==null || words.length == 0){
return al;
}
// now word have at least one item, but may also be empty
for (int i = 0; i < words.length; i++) {
// here i is the start index ,and j is runner to find the ending index;
int j, curSumLength=0, nextSumLength;
int endOfLine = 0;
// find j where it JUST acceed length L
for (j = i ; j < words.length; j++) {
// add 1 because of ' '
nextSumLength = curSumLength + words[j].length();
if(j!= i){// will have a space before it
nextSumLength++;
}
if (nextSumLength <= L) {
endOfLine = j;
curSumLength = nextSumLength;
} else {
break;
}
}
al.add(packStrings(words, i, endOfLine, L));
i = j - 1; // because j is already the next value,
// there is i++ in the for loop, so we -1 here
}
return al;
}
private String packStrings(String[] words, int start, int end, int L) {
StringBuffer buf = new StringBuffer();
if (end == words.length - 1) {
// it should be left justified and no extra space is inserted
// between words.
for (int i = start; i < end; i++) {
buf.append(words[i] + " ");
}
buf.append(words[end]);
buf.append(paddingSpace(L-buf.length()));
return buf.toString();
} else {// padding by adding extra ' '
// find the length of all words
int lengthSum = 0;
for (int i = start; i <= end; i++) {
lengthSum += words[i].length();
}
// calculate how many white space should be added
int numExtraSpace = L - lengthSum ;
int numGaps = end - start;
int baseGapSize ,numOfMod;
if(numGaps == 0){
baseGapSize = numExtraSpace;
numOfMod = 0;
}else{
baseGapSize = numExtraSpace / numGaps;
numOfMod = numExtraSpace % numGaps;
}
for (int i = start; i < end; i++) {
int ifAddOne = (i - start) < numOfMod ? 1 : 0;
int numWhiteSpace = baseGapSize + ifAddOne;
buf.append(words[i] + paddingSpace(numWhiteSpace) );
}
// add the last word
buf.append(words[end]);
buf.append(paddingSpace(L-buf.length()));// in case only one word on this line
return buf.toString();
}
}
private String paddingSpace(int n) {
// return n number of spaces
String str = new String();
for (int i = 0; i < n; i++) {
str += " ";
}
return str;
}
}
Mistakes:
1: OK， 当i= words.length的时候， 我们再直接用 j=i+1;是不太行的。 还是应该从 j=i开始
2： when couting the size of a word, we should also count the spaces between them.
3: 因为在设置endOfLine 的时候， 是通过调用j 来实现的， 但是，j又是从i+1开始的， 所以就总是miss 掉最后一行。
4: 当设置一个数字为 要作为除数时， 首先就应该考虑 divided by zero 问题。 例如这里：
numGaps = end - start;
5：输入的数组为empty的时候，输出应该是有个 space 的-----------> 这个要求，有点儿没有道理吧？？？ 题意理解不对，最后一行，是都补充到最后边
因此，仔细研读corner case之后，
只要加了这么一句， 就可以通过了
buf.append(paddingSpace(L-buf.length()));// in case only one word on this line
Learned:
1: String[] words = {""}; 这里， words的长度不是0， 是1
-------------------------第二遍----------把输入的数组，搞成ArrayList<String> --------每次只需要删去第一个就行了。-----------------
-------------搞到最后， 有一个结果， LC上和Eclipse上不同，不知道为什么-----------哎----
public class Solution {
public ArrayList<String> fullJustify(String[] words, int L) {
ArrayList<String> wordList = new ArrayList<String>();
ArrayList<String> resultList = new ArrayList<String>();
// put words into the wordList, to faciliate deleting
for (int i = 0; i < words.length; i++)
wordList.add(words[i]);
while (!wordList.isEmpty()) {
int curLength = 0; // current length for words only
int curIndex = -1; //
for (int i = 0; i < wordList.size(); i++) {
curLength += wordList.get(i).length();
if (curLength + i > L) { // add i, means we add i space
curIndex = i - 1;
break;
}
}
extractString(wordList, curIndex, L, resultList);
}
return resultList;
}
private void extractString(ArrayList<String> wordList, int curIndex, int L,
ArrayList<String> resultList) {
StringBuffer buf = new StringBuffer();
if (curIndex == 0) { // only one word exist, adding the second would
// exceed L
buf.append(wordList.remove(curIndex));
buf.append(getSpaceString(L - buf.length()));
resultList.add(buf.toString());
return;
}
if (curIndex == -1) { // we reach the last line
// it should be left justified and no extra space is inserted
// between words.
while (!wordList.isEmpty())
buf.append(wordList.remove(0) + " ");
// delete last space of buf. in case it would exceed L
buf.deleteCharAt(buf.length() - 1);
while (buf.length() < L) {
buf.append(" ");
}
resultList.add(buf.toString());
return;
}
// curIndex > 0 , there are gap to hold space
int totalWord = 0;
for (int i = 0; i <= curIndex; i++) {
totalWord += wordList.get(i).length();
}
if (curIndex == 1) { // no space between words
int nSpace = L - totalWord;
buf.append(wordList.remove(0));
buf.append(getSpaceString(nSpace));
buf.append(wordList.remove(0));
resultList.add(buf.toString());
return;
}
// NOW, curIndex >= 2, here ,curIndex is also the number of gaps
int nEvenSpace = (L - totalWord) / curIndex;
int nMoreSpace4Last = (L - totalWord) - nEvenSpace * curIndex;
for (int i = 0; i < curIndex; i++) {
buf.append(wordList.remove(0));
buf.append(getSpaceString(nEvenSpace));
}
buf.append(getSpaceString(nMoreSpace4Last));// add more space in last
// gap position
buf.append(wordList.remove(0)); // add the last word
resultList.add(buf.toString());
}
private String getSpaceString(int nSpace) {
char[] chars = new char[nSpace];
for (int i = 0; i < nSpace; i++) {
chars[i] = ' ';
}
String result = new String(chars);
return result;
}
}
错误：
1： 题意理解错误： 最后一行，是中间只加一个space，最后还是要补够space 达到L的。
| Input: | [""], 2 |
| Output: | [""] |
| Expected: | [" "] |
for(int i =0;i<wordList.size();i++){
buf.append(wordList.remove(0) + " ");
} 这里犯的错误，就是wordList.size 是会变小的。 不能这么用。改成如下代码：
while (!wordList.isEmpty())
buf.append(wordList.remove(0) + " ");
------------------------------------------3 rd Pass----------------------------------------
这次是直接在words上面更改，在各个string后面加上空格， 来满足
Error：
1： 刚开始 nWordAfterStart 这个变量的定义没有给清楚， 因此，编程的时候，就有点儿乱。
前后改成： nWordUsed, , nSpace,,和stepWidth
哎， ， 最后才给换成了 end , 用后面的坐标而不是什么狗屁长度来代表。
2: 当我们发觉出去totalWordLength + nWordAfterSpace 已经超出了界限之后。 不能直接就加入。
因为这个时候，还有可能是 原本就超了长度L了， 。 因此，还要检测 是否>L
3: 当我们用end的时候， 当end是最后一个的时候， 我们要通过和n-1比较大小，而不是n 的比较，来确定是否是最后一个。
4： 当中间情况的时候，我们就是要求在中间加空格。但是，这个时候，却没有考虑，如果只有呢？？ 就只能在后面加空格了。
public class Solution {
public ArrayList<String> fullJustify(String[] words, int L) {
ArrayList<String> al = new ArrayList<String>();
int n = words.length;
int start = 0;
while (start < words.length) {
int totalWordLen = words[start].length();
int end = start; // end position is inclusive in current line
while (end + 1 < n && totalWordLen + end+ 1 - start + words[end + 1].length() <= L) {
totalWordLen += words[end + 1].length();
end++;
}
if (end >= n-1 && totalWordLen + end - start <= L) {
String str = "";
for (int i = start; i < words.length - 1; i++)
str += words[i] + " ";
str += words[words.length - 1]; // add the last one
while (str.length() < L)
str += " ";
al.add(str);
return al;
} else { // step width just exceed the L, go back one
int nSpaceNeeded = L - totalWordLen;
if( start == end){ // we have only one word
for(int i =0;i< nSpaceNeeded;i++)
words[end] += " ";
}else{ // do not add after the end word
while (nSpaceNeeded > 0) {
for (int i = start; i < end; i++) {
words[i] += " ";
nSpaceNeeded--;
if (nSpaceNeeded <= 0)
break;
}
}
}
// now attach all the list from start to end to the result
String str = "";
for (int i = start; i <= end; i++)
str += words[i];
al.add(str);
start = end+1;
}
}
return al;
}
}
No comments:
Post a Comment