68. Text Justification

本文主要是介绍68. Text Justification，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/text-justification/description/
给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。

思路：用一个cur记录一行的输出，用num_of_letters记录字符数。遍历每个单词，若总单词长度加上单词间空格已经超过maxWidth，就输出，否则cur继续填充

精髓在于如何保证左侧放置的空格数要多于右侧的空格数，见下面代码，先计算所需括号数，然后对cur中的0~len(cur)-1号元素逐一进行填充来保证。

for i in range(maxWidth - num_of_letters):cur[i%(len(cur)-1 or 1)] += ' '

最后一行用py的ljust（）方法来左对齐。

class Solution:def fullJustify(self, words, maxWidth):""":type words: List[str]:type maxWidth: int:rtype: List[str]"""res, cur, num_of_letters = [], [], 0for w in words:#检查：当前字符数+空格数+新的单词长度if num_of_letters + len(cur) + len(w) > maxWidth:#填充括号for i in range(maxWidth - num_of_letters):cur[i%(len(cur)-1 or 1)] += ' 'res.append(''.join(cur))cur = []num_of_letters = 0cur += [w]num_of_letters += len(w)res += [' '.join(cur).ljust(maxWidth)]  #最后一行return res

这篇关于68. Text Justification的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---