LeetCode 68. Text Justification
Description
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 "
]
描述
給定一個(gè)單詞數(shù)組和一個(gè)寬度maxWidth蔓倍，格式化文本臂拓，使每行具有正確的maxWidth字符并完全（左和右）對(duì)齊荤牍。
你應(yīng)該使用貪婪的方式處理每一行; 也就是說(shuō)破喻，在每行中包含盡可能多的單詞。 必要時(shí)填充額外的空格，以便每行具有正確的maxWidth字符。
單詞之間的額外空格應(yīng)盡可能均勻分布赊抖。 如果一行上的空格數(shù)不均勻分配，則左側(cè)的空插槽將分配比右側(cè)插槽更多的空格寨典。
對(duì)于最后一行文本熏迹，它應(yīng)該是左對(duì)齊的，并且在單詞之間不插入額外的空格凝赛。
注意：
單詞定義為僅由非空格字符組成的字符序列注暗。
每個(gè)單詞的長(zhǎng)度保證大于0且不超過(guò)maxWidth。
輸入數(shù)組字包含至少一個(gè)字墓猎。
思路
- 這道題并沒(méi)有考察特別的算法捆昏，按照題目要求處理即可.
- 題意是給定一些單詞，給定一行的最大寬度maxWidth（即最多能夠放多少個(gè)字符）毙沾，讓把這些單詞按行放置骗卜，
- 要求：盡可能多的放置單詞在每一行中，每個(gè)單詞之間空格隔開(kāi)左胞，空格均勻分布寇仓，且左邊的空格數(shù)大于右邊的空格數(shù)
- 例如一行有四個(gè)單詞，四個(gè)單詞占據(jù)了9個(gè)字符烤宙，一行允許有16個(gè)字符：則四個(gè)單詞需要三個(gè)間隔遍烦，三個(gè)間隔共占據(jù)7個(gè)空格
- 每個(gè)間隔的空格數(shù)為：3，2躺枕，2
- 我們使用nums表示單詞個(gè)數(shù)服猪，count來(lái)表示已經(jīng)占據(jù)的字符個(gè)數(shù),words數(shù)組中從下標(biāo)i到j(luò)的單詞一共需要占據(jù)如下公式個(gè)字符：
- 因?yàn)槊總€(gè)單詞至少都要一個(gè)空格(最后一個(gè)單詞是不需要的空格的，單獨(dú)處理)
- 當(dāng)count大于等于最大寬度的時(shí)候拐云，我們開(kāi)始填入一行
- 如果count>maxWidth+2:表示count中的最后一個(gè)單詞需要填在下一行罢猪，我們讓nums減去1，count減去最后一個(gè)單詞與一個(gè)空格的長(zhǎng)度.
- evenspace表示每個(gè)單詞（除去最后一個(gè)單詞）都能分配到的字符叉瘩，lastspace表示剩余的字符
- 我們?yōu)閱卧~分配一個(gè)evenspace個(gè)數(shù)的空格字符串膳帕，然后檢查lastspace是否大于0，若是則再給單詞分配一個(gè)空格.
- 我們最后再把最后一個(gè)單詞填入當(dāng)前行
from pprint import pprint
class Solution:
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
wordsnum, nums, count, res, sequence = len(words), 0, 0, [], []
if not wordsnum:
return None
i = 0
while i < wordsnum:
# 記錄當(dāng)前的所有索引
sequence.append(i)
# 記錄當(dāng)前已經(jīng)占據(jù)的字符個(gè)數(shù)
count += len(words[i])+1
# 記錄當(dāng)前的單詞個(gè)數(shù)
nums += 1
# 如果當(dāng)前占據(jù)的字符個(gè)數(shù)已經(jīng)超過(guò)了最大寬度
if count >= maxWidth:
# 如果是嚴(yán)格超出了一個(gè)單詞
if count >= maxWidth+2:
# 當(dāng)前已經(jīng)占據(jù)的寬度減去最后一次添加的單詞長(zhǎng)度薇缅，減去一個(gè)空格
count = count - 1 - len(words[i])
# 單詞個(gè)數(shù)減一
nums = nums - 1
# 單詞索引回退一個(gè)
i = i-1
# 數(shù)組彈出最后一個(gè)單詞的索引
sequence.pop()
# 空格字符的個(gè)數(shù) = 最大寬度 - 所有單詞所占據(jù)的個(gè)數(shù)
space = maxWidth - (count - nums)
# 如果當(dāng)前行不止一個(gè)單詞
if nums > 1:
# 每個(gè)單詞（除去最后一個(gè)單詞危彩，因?yàn)樗恍枰紦?jù)空格）能夠被平均分配的空格
evensapce = space//(nums-1)
# 剩余的空格數(shù)，這些空格將從前往后捅暴，依次分配給每個(gè)單詞恬砂，每個(gè)單詞分配一個(gè)空格咧纠，直到所有的空格都分配完為止
lastspace = space % (nums-1)
else:
# 如果只有一個(gè)單詞蓬痒，則所有的空格都將被分配給它
lastspace = space
line = ''
# 從前往后為每一個(gè)單詞分配空格（最后一個(gè)不分配）
for index in sequence[:-1]:
line += words[index]+' '*evensapce
if lastspace > 0:
line += ' '
lastspace -= 1
# 填入最后一個(gè)單詞：在單詞個(gè)數(shù)不止一個(gè)的情況下lastspace==0，在只有一個(gè)單詞的情況下lastspace可能不為0
# 如果單詞長(zhǎng)度 == maxWidth漆羔，即使只有一個(gè)單詞梧奢，lastspace也為零狱掂，所以說(shuō)"在只有一個(gè)單詞的情況下lastspace可能不為0"
line += words[sequence[-1]]+" "*lastspace
# 在結(jié)果數(shù)組中添加當(dāng)前結(jié)果
res.append(line)
# 重置 nums, count, sequence
nums, count, sequence = 0, 0, []
del line
i += 1
if sequence:
line = ''
for index in sequence:
line += words[index]+' '
line += ' '*(maxWidth - count)
res.append(line)
del line
return res
if __name__ == "__main__":
so = Solution()
res = so.fullJustify(
["What", "must", "be", "acknowledgment", "shall", "be"], 16)
pprint(res)
源代碼文件在這里.
?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載亲轨，轉(zhuǎn)載需保留文章來(lái)源趋惨，作者信息和本聲明.
