一、题目
1、算法题目
“给定单词数组和一个长度maxWidth，重新排版单词，使其成为恰好有maxWWidth个字符，且左右对齐的文本。”
题目链接：
来源：力扣（LeetCode）
链接：68. 文本左右对齐 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定一个单词数组和一个长度 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", 因为最后一行应为左对齐，而不是左右两端对齐。 第二行同样为左对齐，这是因为这行只包含一个单词。 复制代码
二、解题
1、思路分析
这个题根据题干描述的贪心算法，需要确定的是每一行放置多少个单词，从而确定单词之间的空格个数。
对于填充空格的情况可以分为三种：
- 最后一行：单词左对齐，单词之间应只有一个空格，在行末补充空格
- 不是最后一行且只有一个单词：该单词左对齐，在行末补充空格
- 不是最后一行且不只一个单词：将空格均匀的分配在单词之间
2、代码实现
代码参考：
public class Solution { public IList<string> FullJustify(string[] words, int maxWidth) { IList<string> ans = new List<string>(); int right = 0, n = words.Length; while (true) { int left = right; // 当前行的第一个单词在 words 的位置 int sumLen = 0; // 统计这一行单词长度之和 // 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格 while (right < n && sumLen + words[right].Length + right - left <= maxWidth) { sumLen += words[right++].Length; } // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格 if (right == n) { StringBuilder sb = Join(words, left, n, " "); sb.Append(Blank(maxWidth - sb.Length)); ans.Add(sb.ToString()); return ans; } int numWords = right - left; int numSpaces = maxWidth - sumLen; // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格 if (numWords == 1) { StringBuilder sb = new StringBuilder(words[left]); sb.Append(Blank(numSpaces)); ans.Add(sb.ToString()); continue; } // 当前行不只一个单词 int avgSpaces = numSpaces / (numWords - 1); int extraSpaces = numSpaces % (numWords - 1); StringBuilder curr = new StringBuilder(); curr.Append(Join(words, left, left + extraSpaces + 1, Blank(avgSpaces + 1))); // 拼接额外加一个空格的单词 curr.Append(Blank(avgSpaces)); curr.Append(Join(words, left + extraSpaces + 1, right, Blank(avgSpaces))); // 拼接其余单词 ans.Add(curr.ToString()); } } // Blank 返回长度为 n 的由空格组成的字符串 public string Blank(int n) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; ++i) { sb.Append(' '); } return sb.ToString(); } // Join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串 public StringBuilder Join(string[] words, int left, int right, string sep) { StringBuilder sb = new StringBuilder(words[left]); for (int i = left + 1; i < right; ++i) { sb.Append(sep); sb.Append(words[i]); } return sb; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(m)
其中m是数组words中所有字符串的长度之和。
空间复杂度： O(m)
其中m是数组words中所有字符串的长度之和。
三、总结
先分词，再排版。
排版的时候做一个空格集合，然后动态添加。
