給定一個單詞數(shù)組和一個長度 maxWidth，重新排版單詞，使其成為每行恰好有 maxWidth 個字符，且左右兩端對齊的文本。
你應(yīng)該使用“貪心算法”來放置給定的單詞；也就是說，盡可能多地往每行中放置單詞。必要時可用空格
' '填充，使得每行恰好有 maxWidth 個字符。要求盡可能均勻分配單詞間的空格數(shù)量。如果某一行單詞間的空格不能均勻分配，則左側(cè)放置的空格數(shù)要多于右側(cè)的空格數(shù)。
文本的最后一行應(yīng)為左對齊，且單詞之間不插入額外的空格。
說明:
- 單詞是指由非空格字符組成的字符序列。
- 每個單詞的長度大于 0，小于等于 maxWidth。
- 輸入單詞數(shù)組
words至少包含一個單詞。- 示例:
輸入: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 輸出: [ "This is an", "example of text", "justification. " ]
讀題
- 每一行的最大長度限定為 maxWidth，要求文本左右兩端對齊。
- 每一行每一個非結(jié)尾單詞，都得后跟一個空格。
- 每一行不夠 maxWidth時，就得在單詞之間加空格補充。
- 如果某一行單詞總長度不夠 maxWidth，但是又無法均分到單詞間隔時，多余的空格就優(yōu)先從這一行的左往右分布。要求均勻。
- 文本最后一行左對齊，不夠 maxWidth 就尾部補齊。
解題思路(c++貪心詳細題解3種情況)
其實讀完這個題，基本上就有個朦朧的思路了。大體區(qū)分 3 種情況
- 當前是最后一行，就左對齊，小于 maxWidth 的話就尾部補齊空格。
- 當前行只有一個單詞，左對齊，小于 maxWidth 的話就尾部補齊空格。
- 當前行不止一個單詞，也不是最后一行。那就得計算是否需要插入空格補位，如果要就得往里面插入。
這個思路還是比較直觀的。而且第1、2種情況相對來說就比較好處理，可能第3種情況相對來說處理起來有點麻煩。
麻煩點在于我們讀題后知道的：如果某一行單詞總長度不夠 maxWidth，但是又無法均分到單詞間隔時，多余的空格就優(yōu)先從這一行的左往右分布。要求均勻。
按照這個規(guī)則，我們想知道一行都有幾個單詞間隔（坑位）都各自需要補充多個空格。就得計算每一行已經(jīng)有多少個單詞 eWordsCount ，eWordsCount - 1就是坑位數(shù)，maxWidth - 每一行的單詞總長 eLineLen 度就等于總共需要補充的空格數(shù) eBlankCount 。然后我們就可以計算每個坑位最少需要填補的空格個數(shù) eAvg，即 eAvg = eBlankCount / (eWordsCount - 1);，但是可能會不夠均分，按照題意就從左往右補，總共補 extraBlank = eBlankCount % (eWordsCount - 1);。
情況3舉個例子吧：
代碼（帶詳細注釋）
class Solution {
public:
vector<string> fullJustify(vector<string> &words, int maxWidth) {
// 結(jié)果
vector<string> res;
int size = words.size();
// 每一行開始和結(jié)束
int eLeft = 0, eRight = 0;
// 記錄每一行單詞長度和
int eLineLen = 0;
// 當前行單詞個數(shù)
int eWordsCount = 0;
// 當前行需要補缺的長度
int eBlankCount = 0;
// 當前行需要補空格的最少個數(shù)
int eAvg = 0;
// 當前行補完兩個單詞簡的坑位后還多余的 空格個數(shù)
int extraBlank = 0;
while(1) {
eLeft = eRight;
eLineLen = 0;
// 判斷：當前行已有長度 + 下一個單詞的長度 + 每個單詞后需要加多的空格數(shù) <= 20
while (eRight < size && eLineLen + words[eRight].length() + eRight - eLeft <= maxWidth) {
eLineLen += words[eRight++].length();
}
// 情況1：當前行是最后一行
if (eRight == size) {
// 單詞左對齊，且單詞之間應(yīng)只有一個空格
string s = words[eLeft];
for (int i = eLeft + 1; i < size; i++) {
s += ' ' + words[i];
}
//在行尾補充剩余空格
res.push_back(s + string(maxWidth - s.length(), ' '));
return res;
}
// 當前行單詞個數(shù)
eWordsCount = eRight - eLeft;
// 當前行需要補缺的長度
eBlankCount = maxWidth - eLineLen;
// 情況2：當前行只有一個單詞
if (eWordsCount == 1) {
// 單詞左對齊，在行尾補充剩余空格
res.push_back(words[eLeft] + string(eBlankCount, ' '));
continue;
}
/* 情況3：當前行不只一個單詞
首先計算每一行兩個單詞之間 缺失的最少空格數(shù)，因為可能會多余出來，比如一行一共缺8個空格，但是有3個單詞間隔，就不能平均分，按照題意要盡量均勻，左邊優(yōu)先。
此處 我是把每個單詞后應(yīng)該有的空格和 補缺空格一并處理，沒有做區(qū)分。
*/
eAvg = eBlankCount / (eWordsCount - 1);
extraBlank = eBlankCount % (eWordsCount - 1);
string s1 = "";
for (int i = eLeft; i < eRight; i++) {
if (i == eRight - 1) {
s1 += words[i];
}else {
if (i - eLeft < extraBlank) {
s1 += words[i] + string(eAvg + 1, ' ');
}else {
s1 += words[i] + string(eAvg, ' ');
}
}
}
res.push_back(s1);
}
return res;
}
};
其他
另外，也整了個LeetCode題目詳解，堅持費曼學(xué)習(xí)法，吃進去，產(chǎn)出來。
如果感覺本題解對你有幫助，請不要吝嗇點贊????啊 沖沖沖...
