面试经典题---68.文本左右对齐

68.文本左右对齐

我的解法：

两层while循环嵌套，外层循环用于处理不同行，内层while循环计算出每行应有的单词个数。

• 使用left和right记录一行中应有的单词下标，即当前行应包含从words[left]到words[right-1]这count个单词；
• 每行单词之间至少有space/(count-1)个空格，另外每行前space%(count-1)个单词之间应该多一个空格，才能保证空格均匀分配且左侧空格数更多；
• 这里定义了拼接函数join()，用于将words[left]到words[right-1]这些单词以空格space连接起来，注意其中tmp的初值和赋值方式；
• 对于最后一行和只包含一个单词的中间行需要特殊处理

class Solution {string join(vector<string>& words, int left, int right, string space){string tmp = words[left];for(int i = left + 1; i <= right; ++i){tmp += space + words[i];}return tmp;}
public:vector<string> fullJustify(vector<string>& words, int maxWidth) {int n = words.size();vector<string> res;int right = 0;while(true){int left = right;int len = 0;while((right < n) && (words[right].size() + len + right - left <= maxWidth)){len += words[right++].size();}if(right == n){string t = join(words, left, n - 1, " ");res.push_back(t + string(maxWidth - t.size(), ' '));break;}int count = right - left;int space = maxWidth - len;if(count == 1){res.push_back(words[left] + string(space,' '));continue;}int avg_space = space / (count - 1);int extra = space % (count - 1);string t1 = join(words, left, left + extra, string(avg_space + 1, ' '));string t2 = join(words,left + extra + 1,right - 1, string(avg_space, ' '));res.push_back(t1 + string(avg_space,' ') + t2);}return res;}
};