Leetcode每日一题

题目链接

思路:
模拟，怎么模拟，首先可以确定的是,我们需要先判断一行最多放几个单词,
单词之间的空格至少有一个，根据这个思路，我们可以得到每一行的单词分别是哪些，接下来需要处理的就是单词之间的空格数量,当只有一个单词时，那么所有空格全部添加到一个单词后面即可，如果有多个单词，根据题目条件，如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。无法整除那么意味着无法平均分配，我们将得到的余数作为左边单词的个数，每添加一个那么多添加一个空格即可。

代码实现：

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<vector<string>> middle;
        vector<string> res;
        int len = 0;
        vector<string> tmp;
        for(auto word: words){
            len += word.size();
            if(len > maxWidth){
                len = word.size();
                middle.push_back(tmp);
                tmp = vector<string>(0);
            }
            tmp.push_back(word);
            len ++;
        }//如果len始终<maxWidth,那么我们将它放入middle中
        if(!tmp.empty()) middle.push_back(tmp);
        string line;
        for(int i = 0;i < middle.size()-1;i ++){
            vector<string> words = middle[i];
            int cnt = words.size();
            if(cnt == 1){
                line += words[0];
                while(line.size() < maxWidth) line += " ";
            }
            else{
                int sum = 0;
                for(auto word: words) sum += word.size();
                int spaces = maxWidth - sum;
                int space = spaces / (cnt-1);
                int remain = spaces - space * (cnt-1);
                string blank = "";
                for(int i = 0;i < space;i ++) blank += " ";
                for(int i = 0;i < remain;i ++){
                    line += words[i];
                    line += blank + " ";
                }
                for(int i = remain;i < cnt - 1;i ++){
                    line += words[i];
                    line += blank;
                }
                line += words[cnt-1];
            }
            res.push_back(line);
            line = "";
        }
        for (auto word: middle[middle.size()-1]) {
            line += word;
            line += " ";
        }
        // 多了一个空格的情况
        if (line.size() > maxWidth) {
            line.pop_back();
        }
        while(line.size() < maxWidth) {
            line += " ";
        }
        res.push_back(line);
        return res;
    }
};```