LeetCode68.文本左右对齐（字符串逻辑题）Michael是个半路程序员-

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:     vector<string> fullJustify(vector<string>& words, int maxWidth) {         vector<string> 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(width+1+words[i].size() <= maxWidth) { //还能加入            line += " "+words[i];            width += 1+words[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:# py3 def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:         ans = []         line = ""         width = 0         wc = 0 def process(wc,line,width): if wc==1:                 line += ' '*(maxWidth-width) return line             space = maxWidth-width             n = space//(wc-1)             pos = wc-1             line = list(line)             size = len(line) for i in range(size-1,-1,-1): if line[i]==' ':                     line.insert(i, ' '*n)                     space -= n                     pos -= 1 if pos > 0 and space%pos==0:                         n = space//pos             line = "".join(line) return line         i = 0 while i < len(words): if len(line)==0:                 line = words[i]                 width = len(words[i])                 wc = 1 else: if width+1+len(words[i]) <= maxWidth:                     line += " "+words[i]                     width += 1+len(words[i])                     wc += 1 else:                     temp = process(wc,line,width)                     ans.append(temp)                     line = ""                     width, wc = 0, 0                     i -= 1             i += 1         line += ' '*(maxWidth-width)         ans.append(line) return ans 

44 ms 13.5 MB