leetcode_68. 文本左右对齐

 68. 文本左右对齐

题目描述：给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

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

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

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

注意:

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

示例 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 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] 由小写英文字母和符号组成
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth

代码思路：

1.  res 列表来存储最终的输出结果；StringBuilder 对象 sb 来构建每一行的文本；整型数组 nums 来存储每个单词的长度
2. 使用一个循环遍历单词数组 words。在每次循环中,算当前行单词的总字符数 count。
3. 如果当前行的总字符数加上当前单词的长度（即最少的空格数）超过了 maxWidth,说明当前行已经满了,需要输出并开始下一行。
   1. 在输出当前行之前,计算需要添加的空格数量。计算出当前行除了最后一个单词之外的总字符数 count，以及需要添加的空格数 blank = maxWidth - count。
   2. 分配空格：如果当前行只有一个单词,在单词后面添加空格即可，反之需要尽可能均匀地分配这些空格。计算每个单词之间应该添加的空格数 b = blank / num(其中 num 是单词数减1)。遍历每个单词,在单词之间添加 b 个空格。如果还有剩余的空格,则从左到右依次添加。
   3. 如果添加完所有空格后,行长度仍然小于 maxWidth,则继续添加空格直到 maxWidth。
   4. 最后将构建好的当前行添加到 res 列表中,并重置 count 和 sb。
4. 最后一行特殊处理：如果最后一行有多个单词，左对齐，两个单词之间添加一个空格,然后在行末添加空格直到达到 maxWidth。如果最后一行只有一个单词,添加空格直到达到 maxWidth。
5. 最后将构建好的最后一行添加到 res 列表中,并返回 res。

        贪心算法的思路,在每次循环中尽可能多地往每一行中放置单词,并根据剩余空格的数量来决定如何分配空格。确保了非最后一行的每一行恰好有 maxWidth 个字符,且尽可能左右两端对齐。

class Solution {public List<String> fullJustify(String[] words, int maxWidth) {List<String> res = new ArrayList<>();StringBuilder sb = new StringBuilder();int[] nums = new int[words.length];for (int i = 0; i < words.length; i++) {nums[i] = words[i].length();}int count = 0;int pre = 0;for (int i = 0; i < nums.length; i++) {count += nums[i];if (count + i - pre > maxWidth) {count -= nums[i];int num = i - 1 - pre;int blank = maxWidth - count;int b = 1;if (num != 0) {b = blank / num;}for (int k = 0; k < num + 1; k++) {sb.append(words[pre + k]);if (k != num) {for (int kk = 0; kk < b; kk++) {sb.append(" ");}if (blank - b * num - k > 0) {sb.append(" ");}}}while (sb.length() < maxWidth) {sb.append(" ");}res.add(sb.toString());count = 0;sb.setLength(0);pre = i--;} else if (i == nums.length - 1 && count > nums[i] && count + i - pre <= maxWidth) {for (int k = pre; k < nums.length; k++) {sb.append(words[k]);if (k != nums.length - 1) {sb.append(" ");}}while (sb.length() < maxWidth) {sb.append(" ");}res.add(sb.toString());} else if (i == nums.length - 1) {sb.append(words[i]);while (sb.length() < maxWidth) {sb.append(" ");}res.add(sb.toString());}}return res;}
}