leetcode刷題筆記六十八題 文本左右對齊
源位址：68. 文本左右對齊
問題描述：
給定一個單詞數組和一個長度 maxWidth，重新排版單詞，使其成為每行恰好有 maxWidth 個字元，且左右兩端對齊的文本。
你應該使用“貪心算法”來放置給定的單詞；也就是說，盡可能多地往每行中放置單詞。必要時可用空格 ' ' 填充，使得每行恰好有 maxWidth 個字元。
要求盡可能均勻配置設定單詞間的空格數量。如果某一行單詞間的空格不能均勻配置設定，則左側放置的空格數要多于右側的空格數。
文本的最後一行應為左對齊，且單詞之間不插入額外的空格。
說明:
單詞是指由非空格字元組成的字元序列。
每個單詞的長度大于 0，小于等于 maxWidth。
輸入單詞數組 words 至少包含一個單詞。
示例:
輸入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
輸出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:
輸入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
輸出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解釋: 注意最後一行的格式應為 "shall be " 而不是 "shall be",
因為最後一行應為左對齊，而不是左右兩端對齊。
第二行同樣為左對齊，這是因為這行隻包含一個單詞。
示例 3:
輸入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
輸出:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
代碼補充：
/**
本題需要考慮的細節較多
ans => 存儲結果
last => 本層最初的位置
cur => 本層目前位置
floorLength => 本層已存儲詞（詞後會保留一個空格）
視目前詞能否放入分為兩種情況
1.目前詞能夠放入，更新cur和floorLength
2.目前詞不能夠放入， 這種情況分為單個詞和多個詞處理
最後需要考慮的最後一行的處理
*/
import scala.collection.mutable
object Solution {
def fullJustify(words: Array[String], maxWidth: Int): List[String] = {
val ans = mutable.ListBuffer[String]()
var last = 0
var cur = 1
var floorLength = words(0).length
while(cur < words.length && floorLength <= maxWidth){
val tempLength = floorLength + words(cur).length + 1
println(tempLength)
if (tempLength <= maxWidth){
cur += 1
floorLength = tempLength
}
else{
val buckets = cur - last
val space = maxWidth - floorLength
if (buckets == 1){
ans += (words(last) + " "*space)
}
else{
//quo為平均配置設定的每個詞後的空格
val quo = space/(buckets-1)
//rem為配置設定後剩餘的空格
val rem = space%(buckets-1)
val str = new StringBuilder
//将rem中剩餘的空格一一配置設定給左邊的詞
for(i <- 0 until rem) str ++= (words(last+i) + " " *(quo+2))
//右邊的詞隻添加quo和計算中預設的一個空格
for(i <- rem until buckets-1) str ++= (words(last+i) + " "*(quo+1))
//将最後一個詞挂上
str ++= words(cur-1)
ans += str.toString
}
//目前層次處理完 更新結果
last = cur
cur = last + 1
floorLength = words(last).length
}
}
//lastLine
//floorLength不為0的情況，說明為最後一層
//将所有詞切片其後放入空格，再在尾部添加滿足maxWidth的空格
if (floorLength > 0){
val temp = words.slice(last ,words.length).mkString(" ")
ans += (temp + " " * (maxWidth - temp.length))
}
//test
return ans.toList
}
}