专栏首页蛮三刀的后端开发专栏[Leetcode][python]Text Justification/文本左右对齐

[Leetcode][python]Text Justification/文本左右对齐

题目大意

来自:https://shenjie1993.gitbooks.io/leetcode-python/068%20Text%20Justification.html 把一个集合的单词按照每行L个字符存放,不足的在单词间添加空格,每行要两端对齐(即两端都要是单词),如果空格不能均匀分布在所有间隔中,那么左边的空格要多于右边的空格,最后一行靠左对齐,每个单词间一个空格。

注意点: 单词的顺序不能发生改变 中间行也可能出现只有一个单词,这时要靠左对齐 每行要尽可能多的容纳单词

解题思路

参考:https://shenjie1993.gitbooks.io/leetcode-python/068%20Text%20Justification.html 采用双指针的方法来标记当前行的单词,如果加上下一个单词的长度和每个单词间至少一个空格时的总长度大于目标长度,说明此时的单词就是该行应该存放的。要分是否只有一个单词还是多个单词进行讨论,如果有多个单词,需要平均分配单词间的空格。现在可以知道总的空格数和单词间隔数,所以计算单词间的间隔比较简单,注意多余的空格要优先添加到左边的单词间隔中。不要忘记添加最后一行的单词。

代码

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        start = end = 0
        result, curr_words_length = [], 0
        for i, word in enumerate(words):
            if len(word) + curr_words_length + end - start  > maxWidth:
                if end - start == 1:
                    result.append(words[start] + ' ' * (maxWidth - curr_words_length))
                else:
                    total_space = maxWidth - curr_words_length
                    space, extra = divmod(total_space, end - start - 1)
                    for j in range(extra):
                        words[start + j] += ' '
                    result.append((' ' * space).join(words[start:end]))
                curr_words_length = 0
                start = end = i
            end += 1
            curr_words_length += len(word)
        result.append(' '.join(words[start:end]) + ' ' * (maxWidth - curr_words_length - (end - start - 1)))
        return result

总结

自己写了很久,测试集24个通过16个,卡在了单词中自带/符号的,太坑了,不写了。

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        if words == ['']:
            return [' ' * maxWidth]
        result = []
        word_temp = []
        length_temp = 0
        length_each_temp = 0
        string = ''
        for i, word in enumerate(words):
            word_temp.append(word)
            length_temp += len(word)+1
            print i, word
            print word_temp, length_temp
            if length_temp > maxWidth+1:
                word_use = word_temp[:-1]
                print 'word_use', word_use
                if len(word_use) == 1:
                    result.append(word_use[0] + ' ' * (maxWidth-len(word_use[0])))
                elif len(word_use) == 2:
                    result.append(word_use[0] + ' ' * (maxWidth-(len(word_use[0])+len(word_use[1]))) + word_use[1])
                else:
                    for each_word in word_use:
                        length_each_temp += len(each_word)
                    print 'length_each_temp', length_each_temp
                    space_num = maxWidth - length_each_temp
                    print 'space_num', space_num
                    space = space_num // 2
                    print 'space', space
                    if space_num % 2 == 1:  # 不均匀
                        string += word_use[0] + ' ' * (space+1)
                        print string
                        for j in range(1, len(word_use)):
                            string += word_use[j] + ' ' * space
                            print string
                    else:
                        for each_word in word_use:
                            string += each_word + ' ' * space
                    print 'string', len(string), string
                    if space:
                        string = string[:-space]
                    result.append(string)
                word_temp = word_temp[-1:]
                length_temp = len(word_temp[0]) + 1
                length_each_temp = 0
                string = ''        
            print '----------'
        if word_temp:
            for word in word_temp:
                string += word + ' '
            result.append(string + ' ' * (maxWidth-len(string)))
        if len(result[-1]) != maxWidth:
            result[-1] = result[-1][:maxWidth]
        return result

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Leetcode][python]Group Anagrams/字母异位词分组

    后端技术漫谈
  • [Leetcode][python]Substring with Concatenation of All Words/与所有单词相关联的字串

    现有一组长度相等的字符串words,要在原字符串中找出正好包含words中所有字符串的子字符串的起始位置。 例子: 输入: s = “barfoothe...

    后端技术漫谈
  • [Leetcode][python]Word Ladder/Word Ladder II/单词接龙/单词接龙 II

    给定一个起始字符串和一个目标字符串,现在将起始字符串按照特定的变换规则转换为目标字符串,求最少要进行多少次转换。转换规则为每次只能改变字符串中的一个字符,且每次...

    后端技术漫谈
  • Bytes 陷阱, Redis 数据类型的一个小坑

    在Python 3环境下,当我们把一个字符串写进 Redis 再读出来,会发现这个字符串变成了 bytes型的数据:

    青南
  • 文本挖掘和情感分析的基础示例

    经过研究表明,在旅行者的决策过程中,TripAdvisor(猫途鹰,全球旅游点评网)正变得越来越重要。然而,了解TripAdvisor评分与数千个评论文本中的每...

    AiTechYun
  • LWC 57:720. Longest Word in Dictionary

    LWC 57:720. Longest Word in Dictionary 传送门:720. Longest Word in Dictionary Probl...

    用户1147447
  • 使用 trie 树实现简单的中文分词

    导语:工作中偶尔遇到需要对中文进行分词的情况,不要求非常高的精确度和语境符合度,仅是为了统计某些词出现的热度。本文提供了一种简单易行的中文分词方法。 工作中,偶...

    胖兔子兔胖
  • Android Jetpack - Room

    Room 持久化库提供了一个基于 SQLite 的抽象层,以便在利用 SQLite 的全部功能的同时实现更强大的数据库访问

    SkyRiN
  • 6个应当了解的Java比特币开源项目 原

    比特币是第一种被广泛认可并获得众多支持的数字加密货币,如果你考虑在自己的Java系统中增加对比特币的支持,那么相信下面这6个使用Java开发的比特币开源项目会对...

    用户1408045
  • 技术视角的比特币骗局

    比特币目前现价约13000美元,根据比特币算法,最终将会产生2100万个比特币,整个比特币的市值在2730亿美元,约1.8万亿人民币。 那么比特币到底是什么?为...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券