68. 文本左右对齐 [hard]

https://leetcode-cn.com/problems/text-justification/

给定一个单词数组和一个长度 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                  "
]

通过次数10,111 | 提交次数23,008

First Try

2020-07-29

没有想到合适的捷径，直接按朴素的想法一行行放进去并进行调整。有些可以优化加快的地方不管，先把思路实现了，看看是否存在硬伤，速度还差多少再来优化，但没想到直接一波通过了，那就先这样吧。

一个小技巧是在补空白的时候，使用取余对数组实现循环。

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        # 一行一行的逐渐放进去？

        s_idx, n = 0, len(words)
        rv = []
        while s_idx < n:
            e_idx = s_idx 
            seq = []
            seq_size = 0 
            while e_idx < n:  # TODO: last words
                # 判断把一个新的单词放进去，然后考虑在单词之间放上空格，最经济条件下是否已经超过了长度限制
                # 如果超过长度限制，已经放进去的单词放回去一个。由题意可知每行至少会有1个。
                seq.append(words[e_idx])
                if len(' '.join(seq)) > maxWidth:  # TODO: simplify
                    seq.pop()
                    e_idx -= 1 
                    break 
                else:
                    e_idx += 1 
            # 剩下多余可以用来分配的空格
            space_available = maxWidth - len(' '.join(seq))
            # 如果一行里只能放一个单词，那么左对齐即可
            if len(seq) == 1:
                rv.append(seq[0] + space_available * " ")
                s_idx = e_idx + 1 
                continue 
            # spaces之间的分配
            spaces = [" "] * (len(seq) - 1)
            i = 0 
            while space_available:
                spaces[i % len(spaces)] += " "  # 通过取模实现了循环的效果
                space_available -= 1
                i += 1
            tmp = ""
            for i in range(len(seq)):
                tmp += seq[i]
                if i != len(spaces):  # space空格的数量总归比单词要少1个
                    tmp += spaces[i]
            rv.append(tmp)
            s_idx = e_idx + 1
        # 最后一行拿出来再额外重新处理
        last_line = rv[-1]
        words = [i.strip() for i in last_line.split(" ") if i.strip()]
        last_line = ' '.join(words)
        last_line = last_line + (maxWidth - len(last_line)) * " "
        rv[-1] = last_line
        return r

执行用时：44 ms, 在所有 Python3 提交中击败了42.21%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了100.00%的用户

68. 文本左右对齐 [hard]​

First Try​

68. 文本左右对齐 [hard]

First Try