个人怎么做网站排名优化,wordpress忘记所有密码,摘要 wordpress,新会网站建设公司一、题目描述 给定一个单词数组 words 和一个长度 maxWidth #xff0c;重新排版单词#xff0c;使其成为每行恰好有 maxWidth 个字符#xff0c;且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词#xff1b;也就是说#xff0c;尽可能多地往每行中放置单…一、题目描述 给定一个单词数组 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三、解题思路
基本思路 贪心算法按顺序累加单词长度如果一旦大于一行最大长度则除去该单词生成一行记得特殊处理一个单词一行和最后一行单词这两种情况都是左对齐。具体思路 预处理定义函数 add_space(int n) 其作用是生成 n 个空格的字符串。定义函数 add_str(int start, int end, int len, int maxWidth, vectorstring words) 其作用是生成一行字符串参数 start 表示该行的首个单词下标end 表示下一行的首个单词下标len 表示该行单词长度不包括空格maxWidth 表示该行长度words 表示所有单词。生成每行字符串按序遍历单词累加单词长度判断累加单词长度应需空格长度是否小于每行最大长度是表示可以容纳该单词则累加单词长度否则表示超过则生成该行并且重置累加单词长度记录该单词下标作为下一行的首个单词下标。后处理最后一定会剩下一行单词没有处理特殊处理最后一行单词拼接单词和必要的空格最后补充空格使其填满一行。
四、参考代码
时间复杂度 O ( n ) \Omicron(n) O(n) 空间复杂度 O ( n ) \Omicron(n) O(n)
class Solution {
public:string add_space(int n) {return string(n, );}string add_str(int start, int end, int len, int maxWidth,vectorstring words) {string str , space ;if (end - start 1) {str words[start] add_space(maxWidth - len);} else {int count (maxWidth - len) / (end - start - 1);int r (maxWidth - len) - count * (end - start - 1);str words[start];for (int j start 1; j end; j) {if (r 0) {str ;r--;}str add_space(count) words[j];}}return str;}vectorstring fullJustify(vectorstring words, int maxWidth) {int n words.size();int len 0, start 0;vectorstring strs;for (int i 0; i n; i) {if (len words[i].length() i - start maxWidth) {len words[i].length();} else {strs.push_back(add_str(start, i, len, maxWidth, words));len 0;start i--;}}// 拼接最后一行string lastwords[start];for(int istart1;in;i){last words[i];}strs.push_back(lastadd_space(maxWidth-last.length()));return strs;}
};
