题解 | #将单词均匀排列# 字符串模拟

知识点

模拟

思路

样例给的很差，和描述不符

同时我认为标程有问题，比如这个测试点

["NiuNiu", "Nowcoder", "onto", "JK", "and", "eat", "grass", "trees"],12

标程给的是 ["NiuNiu      ","Nowcoder    ","onto   JK and","eat grass   ","trees       "]

"onto   JK and" 这一句字母有9个，第一个空白是3个空格，第二个空白是1个空格，一共13个字符，违反了最大值12的要求

具体实现思路就是先贪心找出每一行最大的可加入的单词数，再根据题面的要求分配好空格数，更新答案即可；

AC Code（C++）

// string to_string(string s) { return '"' + s + '"'; }
// string to_string(const char *s) { return to_string((string) s); }
// string to_string(bool b) { return (b ? "true" : "false"); }
// template<typename A, typename B>
// string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
// template<typename A>
// string to_string(A v) { bool first = true; string res = "{"; for(const auto &x : v) { if(!first) { res += ", "; } first = false; res += to_string(x);} res += "}"; return res; }
// void debug_out() { cout << endl; }
// template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cout << " " << to_string(H); debug_out(T...);}
// #define dbg(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 
//      * @param words string字符串vector 
//      * @param maxWidth int整型 
//      * @return string字符串vector
//      */
//     vector<string> arrangeWords(vector<string>& words, int maxWidth) {
//         vector<string> res;
//         int n = words.size();
//         for (int i = 0; i < n; ) {
//             int j = i;
//             int sum = words[j].size();
//             while (j + 1 < n and (sum + words[j + 1].size() + (j + 1 - i)) <= maxWidth) {
//                 sum += words[++ j].size();
//             }
//             string ans = words[i];
//             if (j > i and j != n - 1) {
//                 int space = maxWidth - sum;
//                 int ave = space / (j - i);
//                 space %= (j - i);
//                 dbg(ave, space);
//                 for (int k = i + 1; k <= j; k ++) {
//                     ans += string(ave, ' ');
//                     if (space > 0) {
//                         space -= 1;
//                         ans.push_back(' ');
//                     }
//                     dbg(ave, space);
//                     ans += words[k];
//                 }
//             }
//             else if (j == n - 1) {
//                 for (int k = i + 1; k <= j; k ++) {
//                     ans += " " + words[k];
//                 }
//             }
//             cout << ans << endl;
//             while (ans.size() < maxWidth) ans.push_back(' ');
//             res.push_back(ans);
//             i = j + 1;
//         }
//         return res;
//     }
// };
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param words string字符串vector
     * @param maxWidth int整型
     * @return string字符串vector
     */
    vector<string> arrangeWords(vector<string>& words, int maxWidth) {
        vector<string> result;
        int i = 0;
        while (i < words.size()) {
            int j = i;
            int curWidth = 0;
            while (j < words.size() && (curWidth + words[j].size() + j - i) <= maxWidth) {
                curWidth += words[j].size();
                ++j;
            }
            int space = maxWidth - curWidth;
            string line = words[i];
            if (j < words.size()) {
                for (int k = i + 1; k < j; ++k) {
                    int numSpaces = (j - k == 1 ||
                                     j == words.size()) ? 1 : (space + j - k - 2) / (j - k - 1);
                    line.append(numSpaces, ' ');
                    space -= (numSpaces - 1);
                    line += words[k];
                }
                if (line.size() < maxWidth) {
                    line.append(maxWidth - line.size(), ' ');
                }
            } else {
                for (int k = i + 1; k < j; ++k) {
                    line.push_back(' ');
                    line += words[k];
                }
                if (line.size() < maxWidth) {
                    line.append(maxWidth - line.size(), ' ');
                }
            }
            result.push_back(line);
            i = j;
        }
        return result;
    }
};