Text Justification_leetcode_go
2018-11-09 本文已影响0人
fjxCode
Text Justification做两遍，两种解法
题目：
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth 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 maxWidth 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.
Note:
A word is defined as a character sequence consisting of non-space characters only.
Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.
Example 1:
Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Example 2:
Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be",
because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.
Example 3:
Input:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
思路：
- 完成两件事，按组装填。是否还能再填一个空格，分两个case。分别处理组内空格。
- curWordIdx := make([]int,0)用来修补空格很方便。
- 用i遍历words，回退方便。
- 最后一行左对齐的要求，特殊处理。（不添空格，直接返回）
- 居中的实现：记录间隔的空格，将单词重新放入。拼接字串的方式不容易实现。
- 细节：对某一个解。用数组要填充空格。用字串则不用。
- 在循还体内处理最后一组，上下文变量多，代码好写。
解：
func fullJustify(words []string, maxWidth int) []string {
res := make([]string,0)
curOne := make([]byte,maxWidth)
for idxCurOne:=0;idxCurOne<len(curOne);idxCurOne++{
curOne[idxCurOne] = ' '
}
curIdx :=-1
curWords := make([]string,0)
for j:=0;j<len(words);j++{
if curIdx+len(words[j]) < maxWidth-1{
//默认加上空格，组内处理时再退回
curWords = append(curWords,words[j])
for chIdx:=0;chIdx<len(words[j]);chIdx++{
curIdx++
curOne[curIdx] = words[j][chIdx]
}
curIdx++
curOne[curIdx] = ' '
//最后一组，左对齐，留尾部的空格
if j == len(words)-1{
str := string(curOne)
res = append(res,str)
break
}
}else if curIdx+len(words[j]) == maxWidth-1{
//一组正好加满
for chIdx:=0;chIdx<len(words[j]);chIdx++{
curIdx++
curOne[curIdx] = words[j][chIdx]
}
res = append(res,string(curOne[0:curIdx+1]))
curOne = make([]byte,maxWidth)
for idxCurOne:=0;idxCurOne<len(curOne);idxCurOne++{
curOne[idxCurOne] = ' '
}
curWords = make([]string,0)
curIdx = -1
}else{
//仅有一个单词
if len(curWords) == 1{
res = append(res,string(curOne))
curOne = make([]byte,maxWidth)
for idxCurOne:=0;idxCurOne<len(curOne);idxCurOne++{
curOne[idxCurOne] = ' '
}
curWords = make([]string,0)
curIdx = -1
j--
continue
}
//无法加单词，处理下一组
if curOne[curIdx] == ' '{
curIdx--
}
spaceNum := maxWidth-1-curIdx
spaceInterval := make([]int,len(curWords)-1)
for idx,_ := range spaceInterval{
spaceInterval[idx] = 1
}
for k:=0;k<spaceNum;k++{
idx:= k%len(spaceInterval)
spaceInterval[idx]++
}
curOneS := ""
for k:=0;k<len(spaceInterval);k++{
curOneS+= curWords[k]
for l:=0;l<spaceInterval[k];l++{
curOneS+= " "
}
}
curOneS += curWords[len(curWords)-1]
res = append(res,curOneS)
curOne = make([]byte,maxWidth)
for idxCurOne:=0;idxCurOne<len(curOne);idxCurOne++{
curOne[idxCurOne] = ' '
}
curWords = make([]string,0)
curIdx = -1
j--
}
}
return res
}
附上上次写的代码：
其它mark：Runtime: 0 ms, faster than 100.00% of Go online submissions for Text Justification.通过测试，但运动时间0ms？？？不知道是不是leetcode的bug。
func fullJustify(words []string, maxWidth int) []string {
var res []string
collect := make([]string, 0, len(words))
collectLength := 0
for i := 0; i < len(words); i++ {
collectLengthMayBe := collectLength
if collectLength == 0 {
collectLengthMayBe += len(words[i])
} else {
collectLengthMayBe += len(words[i]) + 1
}
if collectLengthMayBe > maxWidth {
//handle this group
if len(collect) == 1 {
resElem := collect[0]
for i := 0; i<maxWidth-len(collect[0]);i++ {
resElem += " "
}
res = append(res, resElem)
}else {
//hasSpace
var strSpace []string
strSpace = make([]string, len(collect)-1, len(words))
for i := 0; i < len(strSpace); i++ {
strSpace[i] = " "
}
leftSpace := maxWidth - collectLength
for i := 0; leftSpace > 0; i = (i + 1) % len(strSpace) {
strSpace[i] += " "
leftSpace--
}
resElem := ""
for i := 0; i < len(strSpace); i++ {
resElem = resElem + collect[i] + strSpace[i]
}
resElem += collect[len(collect)-1]
res = append(res, resElem)
}
//reset
collect = make([]string, 0, len(words))
collect = append(collect, words[i])
collectLength = len(words[i])
continue
}
collectLength = collectLengthMayBe
collect = append(collect, words[i])
}
//handle the last group
if len(collect) == 1 {
resElem := collect[0]
for i := 0; i<maxWidth-len(collect[0]);i++ {
resElem += " "
}
res = append(res, resElem)
return res
}
//left-justified
resElem := ""
for i := 0; i < len(collect)-1; i++ {
resElem = resElem + collect[i] + " "
}
resElem += collect[len(collect)-1]
//resElem长度是变化的，要先取了来，不能写在循环中
spaceNum :=maxWidth-len(resElem)
for i := 0; i < spaceNum; i++ {
resElem = resElem + " "
}
res = append(res, resElem)
return res
}
