力扣:68. 文本左右对齐(Python3)

这篇具有很好参考价值的文章主要介绍了力扣:68. 文本左右对齐(Python3)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

给定一个单词数组 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:其为一个函数,用来指定取最小值的方法。 

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣:70. 爬楼梯(Python3)

    假设你正在爬楼梯。需要  n  阶你才能到达楼顶。 每次你可以爬  1  或  2  个台阶。你有多少种不同的方法可以爬到楼顶呢? 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 示例 1: 输入:n = 2 输出:2 解释: 示例 2: 输入:n = 3 输出:

    2024年02月11日
    浏览(48)
  • 力扣:60. 排列序列(Python3)

    给出集合  [1,2,3,...,n] ,其所有元素共有  n!  种排列。 按大小顺序列出所有排列情况,并一一标记,当  n = 3  时, 所有排列如下: \\\"123\\\" \\\"132\\\" \\\"213\\\" \\\"231\\\" \\\"312\\\" \\\"321\\\" 给定  n  和  k ,返回第  k  个排列。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成

    2024年02月13日
    浏览(30)
  • 力扣:74. 搜索二维矩阵(Python3)

    给你一个满足下述两条属性的  m x n  整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数  target  ,如果  target  在矩阵中,返回  true  ;否则,返回  false  。 来源:力扣(LeetCode) 链接:力扣(LeetCode)

    2024年02月10日
    浏览(58)
  • 力扣:73. 矩阵置零(Python3)

    给定一个  m x n  的矩阵,如果一个元素为  0  ,则将其所在行和列的所有元素都设为  0  。请使用  原地  算法 。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 示例 1:   输入:matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[1,0,1],[0,0,0],[1,0,1]] 示例

    2024年02月11日
    浏览(34)
  • 力扣:76. 最小覆盖子串(Python3)

    给你一个字符串  s  、一个字符串  t  。返回  s  中涵盖  t  所有字符的最小子串。如果  s  中不存在涵盖  t  所有字符的子串,则返回空字符串  \\\"\\\"  。 注意: 对于  t  中重复字符,我们寻找的子字符串中该字符数量必须不少于  t  中该字符数量。 如果  s  中存在

    2024年02月11日
    浏览(34)
  • 力扣:49. 字母异位词分组(Python3)

    给你一个字符串数组,请你将  字母异位词  组合在一起。可以按任意顺序返回结果列表。 字母异位词  是由重新排列源单词的所有字母得到的一个新单词。 来源:力扣(LeetCode) 链接:力扣 示例 1: 输入:strs = [\\\"eat\\\", \\\"tea\\\", \\\"tan\\\", \\\"ate\\\", \\\"nat\\\", \\\"bat\\\"] 输出:[[\\\"bat\\\"],[\\\"nat\\\",\\\"tan\\\"],[\\\"

    2024年02月14日
    浏览(35)
  • 力扣:67. 二进制求和(Python3)

    给你两个二进制字符串  a  和  b  ,以二进制字符串的形式返回它们的和。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 示例 1: 输入:a = \\\"11\\\", b = \\\"1\\\" 输出:\\\"100\\\" 示例 2: 输入:a = \\\"1010\\\", b = \\\"1011\\\" 输出:\\\"10101\\\" 转成十进制相加,再转回二进

    2024年02月12日
    浏览(31)
  • 力扣:113. 路径总和 II(Python3)

    给你二叉树的根节点  root  和一个整数目标和  targetSum  ,找出所有  从根节点到叶子节点  路径总和等于给定目标和的路径。 叶子节点  是指没有子节点的节点。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 示例 1: 输入:root = [5,4,

    2024年02月07日
    浏览(39)
  • 力扣:69. x 的平方根(Python3)

    给你一个非负整数  x  ,计算并返回  x  的  算术平方根  。 由于返回类型是整数,结果只保留  整数部分  ,小数部分将被  舍去 。 注意: 不允许使用任何内置指数函数和算符,例如  pow(x, 0.5)  或者  x ** 0.5  。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球

    2024年02月12日
    浏览(54)
  • 力扣:150. 逆波兰表达式求值(Python3)

    给你一个字符串数组  tokens  ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意: 有效的算符为  \\\'+\\\' 、 \\\'-\\\' 、 \\\'*\\\'  和  \\\'/\\\'  。 每个操作数(运算对象)都可以是一个整数或者另一个表达式。 两个整数之间的除法总

    2024年02月05日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包