【一天一道LeetCode】#68. Text Justification

一天一道LeetCode

（一）题目

（二）解题

题目大意：按照一定的格式对文本进行对齐。

需要注意以下几点：

1、只有一个单词直接在后面补空格，如“a”，5 输出“a ”

2、最后一组单词不需要对齐，如“a”，“b” 5 输出“a b ”

3、单词与单词之间至少要有一个空格隔开

具体 思路见代码注释：

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ret;//返回值
        int width = words[0].size();
        int num = 1;
        int last = 0 ;//纪录每一次maxWidth的起始序号
        for(int i = 1 ; i<words.size() ; i++)
        {
            width+=words[i].size();
            num++;
            if(width+num-1>maxWidth)//这里要注意每个单词之间要用空格隔开
            {
                width-=words[i].size();//清除掉最后一个数
                num--;
                string temp;
                if(num==1){//只有一个单词的情况
                    temp+=words[i-1];
                    while(temp.size()!=maxWidth) temp+=" ";//在后面补齐空格
                    ret.push_back(temp);
                }
                else//多个单词，但不是结尾的情况
                {
                    int blankWidth = maxWidth - width;
                    int gap = 0;
                    for(int j = last ; j < i ; j++)
                    {
                        if(j==i-1) gap=0;//最后一个单词后面不加空格
                        else {
                            gap = blankWidth/(num-1);//每一次进来都要算需要增加多少空格
                            gap = blankWidth%(num-1)>0?gap+1:gap;//保证均匀分布
                            blankWidth -=gap;
                        }
                        temp+=words[j];
                        while(gap>0&&gap--) temp+=" ";
                        num--;
                    }
                    ret.push_back(temp);
                }
                //初始化下一个循环
                last=i;
                width = words[i].size();
                num=1;
            }
        }
        if(last<words.size()){//考虑末尾不足maxWidth的情况
            int j = last;
            string temp;
            while(j<words.size()){//先按一个空格添加words
                temp+=words[j++];
                if(temp.size()<maxWidth) temp+=" ";
            }
            while(temp.size()<maxWidth) temp+=" ";//最后不足maxWidth就用空格补足
            ret.push_back(temp);
        }
        return ret;
    }
};