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