wordpress导航网站,人才网站查询档案,个人餐饮网站模板,济南 网站建设公司 医疗1. 题目
给定一个单词数组和一个长度 maxWidth#xff0c;重新排版单词#xff0c;使其成为每行恰好有 maxWidth 个字符#xff0c;且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词#xff1b;也就是说#xff0c;尽可能多地往每行中放置单词。必要时可…1. 题目
给定一个单词数组和一个长度 maxWidth重新排版单词使其成为每行恰好有 maxWidth 个字符且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词也就是说尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐且单词之间不插入额外的空格。
说明: 单词是指由非空格字符组成的字符序列。 每个单词的长度大于 0小于等于 maxWidth。 输入单词数组 words 至少包含一个单词。
示例:
输入:
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
]来源力扣LeetCode 链接https://leetcode-cn.com/problems/text-justification 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution { // C
public:vectorstring fullJustify(vectorstring words, int maxWidth) {vectorstring ans;string line;int i, width 0, wc;for(i 0; i words.size(); i){if(line.empty()){ //为空直接加入单词line words[i];width words[i].size();wc 1;//单词个数}else{if(width1words[i].size() maxWidth){ //还能加入line words[i];width 1words[i].size();wc;}else//超了放不下i{process(wc,line,maxWidth,width);//处理单词ans.push_back(line);//该行存入答案line ;width wc 0;i--;}}}line string(maxWidth-width, );//最后一行左对齐后面补空格ans.push_back(line);return ans;}void process(int wc, string line, int maxWidth, int width){if(wc 1)//只有一个单词直接后面补空格{line string(maxWidth-width, );return;}int space maxWidth - width;//需要的空格数int n space/(wc-1);//平均插入个数int pos wc-1;//可以插入的位置个数for(int i line.size()-1; i 0; --i){if(line[i] ){ //找到空格了line.insert(i,n, );//插入平均的个数space - n;//空格数更新pos--;//位置数更新if(pos 0 space%pos 0)//位置还有且能被整除n space/pos;//变成整除的左边空格大于右边条件}}}
};0 ms 7 MB
class Solution:# py3def fullJustify(self, words: List[str], maxWidth: int) - List[str]:ans []line width 0wc 0def process(wc,line,width):if wc1:line *(maxWidth-width)return linespace maxWidth-widthn space//(wc-1)pos wc-1line list(line)size len(line)for i in range(size-1,-1,-1):if line[i] :line.insert(i, *n)space - npos - 1if pos 0 and space%pos0:n space//posline .join(line)return linei 0while i len(words):if len(line)0:line words[i]width len(words[i])wc 1else:if width1len(words[i]) maxWidth:line words[i]width 1len(words[i])wc 1else:temp process(wc,line,width)ans.append(temp)line width, wc 0, 0i - 1i 1line *(maxWidth-width)ans.append(line)return ans44 ms 13.5 MB
