题目:
给定一个单词数组
words
和一个长度maxWidth
,重新排版单词,使其成为每行恰好有maxWidth
个字符,且左右两端对齐的文本。你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可用空格
' '
填充,使得每行恰好有 maxWidth 个字符。要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配,则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐,且单词之间不插入额外的空格。
注意:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0,小于等于 maxWidth。
- 输入单词数组
words
至少包含一个单词。来源:力扣(LeetCode)
链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
示例:
示例 1:
输入: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 "]
解法:
根据题意,单词之间至少1个空格,当单词间空格数不一致时,只有可能前部空格数比后部空格数多1即空格数之间的差的绝对值不可能大于1。
创建空列表result用来存放结果,初始化r为空字符串,用来表示每行内容即存入result的每个元素。
遍历words,分为2种情况,r是否为空,因为r为空时,只需要存入单词(word);当r不为空时,在存放前还要存入空格。接下来分类讨论。
当r为空时,r = word,如果遇到最后1个单词,那么最后1个单词单独成行,行末用空格填充即向result中直接添加word + ' ' * (maxWidth - len(word))。
当r不为空时,分为3种情况,分别是len(r) + 1 + len(word) < maxWidth、len(r) + 1 + len(word) == maxWidth、len(r) + 1 + len(word) > maxWidth即加上当前单词仍然不满maxWidth、加上当前单词正好maxWidth、加上当前单词超过maxWidth。“+1”的含义是算上前后单词间的空格,因为单词间至少需要1个空格,先按1个算,后期(需要换行的时候)再调整。需要分类讨论的原因是对应操作不一样。当不满maxWidth时,直接向r添加就好;当正好maxWidth时,添加后需要加入result,r重置为空;当超过maxWidth时,需要先在单词间填充空格,然后添加到result,再把单词赋值给r。接下来具体分类讨论。
当不满maxWidth时,在r后面添加' ' + word,如果当前是最后1个单词,还需要考虑行末空格填充即直接向result中添加(t := r + ' ' + word) + ' ' * (maxWidth - len(t))。
当正好maxWidth时,直接向result中添加r + ' ' + word,然后r重置为空。
当超过maxWidth时,说明需要换行,先对当前r整理。如果r中只有1个单词,那比较简单,注意行末空格填充即直接向result中添加r + ' ' * (maxWidth - len(r))。如果不止1个单词,需要调整单词间空格数。设total为需要调整的总空格数,用maxWidth-单词总长度-单词间的1个空格计算得到即total = (maxWidth - len(''.join(r.split())) - (len(r.split()) - 1))。设space为平均每个单词间需要多加入的空格即space = total // (len(r.split()) - 1),因为是平均出来的,向下取整,所以还会有剩下的空格,更新total:total %= (len(r.split()) - 1),这些空格逐个从前往后填入单词间。定义row为调整后的行,初始化为r中第1个单词即r.split()[0],然后从r中第2个单词遍历到尾,逐个添加到row中以及调整单词间的空格,重点在于空格,空格数等于1+space+1/0,如果有剩下的,最后就+1,如果没有剩下的,就+0即' ' * (1 + space + (t2 := min(1, total))),然后更新total:total -= t2。遍历完后,把row添加到result。到此换行的整理结束,然后把当前单词赋值给r,如果当前是最后1个单词,注意行末空格填充即直接向result中添加word + ' ' * (maxWidth - len(word))。
知识点:
1.min(arg1, arg2, *args, *[, key=func]):获取最小值。arg1, arg2, *args:参数值,可输入多个参数,比较必须大于2个参数进行比较否则报错。key:其为一个函数,用来指定取最小值的方法。 文章来源:https://www.toymoban.com/news/detail-671034.html
2.关于*:可以用来表示重复(复制)的意思,比如list = [0] * 10,表示创建10个0的列表。文章来源地址https://www.toymoban.com/news/detail-671034.html
代码:
class Solution: def fullJustify(self, words: List[str], maxWidth: int) -> List[str]: result = [] r = '' for index, word in enumerate(words): if len(r) == 0: # 每行第1个 if index != len(words) - 1: r = word else: # 最后1个单词单独成行 result.append(word + ' ' * (maxWidth - len(word))) else: if len(r) + 1 + len(word) < maxWidth: if index != len(words) - 1: r += ' ' + word else: # 最后1行 result.append((t := r + ' ' + word) + ' ' * (maxWidth - len(t))) elif len(r) + 1 + len(word) == maxWidth: if index != len(words) - 1: result.append(r + ' ' + word) r = '' else: # 最后1行 result.append(r + ' ' + word) else: # 需要换行 if len(r.split()) == 1: # 1行只有1个单词 result.append(r + ' ' * (maxWidth - len(r))) else: total = (maxWidth - len(''.join(r.split())) - (len(r.split()) - 1)) space = total // (len(r.split()) - 1) total %= (len(r.split()) - 1) row = r.split()[0] for idx in range(1, len(r.split())): row += ' ' * (1 + space + (t2 := min(1, total))) + r.split()[idx] total -= t2 result.append(row) if index == len(words) - 1: # 最后1个单词单独成行 result.append(word + ' ' * (maxWidth - len(word))) else: r = word return result
到了这里,关于力扣:68. 文本左右对齐(Python3)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!