淄博建设工程学校官方网站,专门做商标的网站有哪些,网站的网站搭建,房地产网站建设报价文章目录 题目描述解题方法贪心java代码复杂度分析 题目描述
给定一个单词数组 words 和一个长度 maxWidth #xff0c;重新排版单词#xff0c;使其成为每行恰好有 maxWidth 个字符#xff0c;且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词#xff… 文章目录 题目描述解题方法贪心java代码复杂度分析 题目描述
给定一个单词数组 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 3001 words[i].length 20words[i] 由小写英文字母和符号组成1 maxWidth 100words[i].length maxWidth
解题方法
贪心
思路就是按照上面的规则来个每一行放置单词。
我们可以总结出以下几种情况。
除最后一行外每一行的单词有两种情况。
当该行单词数 1时需要给单词之间加空格最后一个单词刚好放到末尾后面无空格。当该行单词数 1时只需要给该单词后面加空格。
如果是最后一行除最后一个单词外需要给每个单词后面加一个空格。最后一个单词后面补充剩余的空格。
总结出以上情况后那我们就可以构建思路了。
我们可以记录几个变量curWidth代表当前行的单词长度curNums代表当前行的单词个数words[i]代表下一个要添加的单词。当curWidth words[i].length() curNums maxWidth时当前行就可以加入新单词否则将当前行组成的字符串加入结果集。curWidth和curNums重置为0。
接下来就是怎么添加单词后面的空格了。我们可以计算当前行可以添加的空格数量然后根据上面总结的情况将空格合理分配到单词后面。这块可以看代码实现我已将部分重要的注释加入到代码中。
java代码
public ListString fullJustify(String[] words, int maxWidth) {ListString list new ArrayList();int i 0;// 记录当前行的单词长度int curWidth 0;// 记录当前行的单词个数int curNums 0;while (i words.length) {// 当前行单词长度 下一个单词长度 当前行的单词数量最少空格数量 最大宽度说明可以把下一个单词加入当前行if (curWidth words[i].length() curNums maxWidth) {curWidth words[i].length();curNums;i;} else {// 空格个数int spaces maxWidth - curWidth;int a 0;int b 0;// 当前行单词数 1 时if (curNums - 1 ! 0) {// 除当前行的最后一个单词外每个单词后面至少加a个空格前b个单词后面还需要再加1个空格a spaces / (curNums - 1);b spaces % (curNums - 1);}StringBuilder lineBuilder new StringBuilder();for (int j 0; j curNums - 1; j) {// 加单词lineBuilder.append(words[i - curNums j]);// 加空格for (int k 0; k a; k) {lineBuilder.append( );}if (b-- 0) {lineBuilder.append( );}}// 加当前行的最后一个单词lineBuilder.append(words[i - 1]);// 如果该行只有一个单词需要在单词后面的剩余空间加上空格if (curNums 1) {while (spaces-- 0) {lineBuilder.append( );}}// 当前行加入结果集list.add(lineBuilder.toString());// 当前行加入结果集后当前行宽度和当前行单词个数重置为0curWidth 0;curNums 0;}}StringBuilder lineBuilder new StringBuilder();// 最后一行结果集先加单词再加1个空格for (int j 0; j curNums - 1; j) {lineBuilder.append(words[i - curNums j]);lineBuilder.append( );}// 剩余空格个数int spaces maxWidth - curWidth - (curNums - 1);lineBuilder.append(words[i - 1]);// 最后一个单词后面把剩余空格都加上while (spaces-- 0) {lineBuilder.append( );}// 最后一行加入结果集list.add(lineBuilder.toString());return list;
}复杂度分析
时间复杂度 O ( m ) O(m) O(m) m m m是单词长度总和 空格总和。 空间复杂度 O ( m ) O(m) O(m)结果需要提供 O ( m ) O(m) O(m)的存储空间。 个人公众号 个人小游戏
