68. 文本左右对齐（python,C++）
题目描述（困难）
给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
说明:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0，小于等于 maxWidth。
- 输入单词数组
words至少包含一个单词。
示例:
输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:
输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:
输入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]思路分析
- 遍历单词list中的每一个单词
- 判断每一行的最大单词个数，如果单词长度加上单词间的间隔小于规定每行长度maxWidth，则继续添加单词；否则本行所放的单词个数确定，开始进行单词间间隔几个空格的判定：
- 如果刚好本行所有单词长度加上一个单词间的间隔等于maxWidth，则此行就输出单词，每个单词用一个空格。
- 如果本行所有单词长度加上一个单词间的间隔大于maxWidth，判断距离本行所有单词长度加上一个单词间的间隔等于maxWidth多余的字符数，从左到右依次补在单词间的间隔里。
- 判断是否是最后一行，最后一行每个单词1个空格，距离maxWidth的差距用空格补齐。
为了提高代码的可读性，当确定每一行所放的单词后，确定单词间间隔的判断单独写了一个方法，供主函数调用。总之就是各种条件判断。本题感觉技巧性不强，一根筋做下来花费了我3个小时，提交结果打败了python版的22%用户，挺挫败的。后面附了一个别人C++ 的方法，这个用时0ms，击败了100%用户。后面我也附有将这个版本的C++改为python版，用时44ms，击败89.19%用户。
代码
我的python：
class Solution:
def space(self, words, s, flag):
ans = words[0]
if flag:
if len(words)>1:
for i in words[1:]:
ans = ans + ' '+i
return ans
if len(words)>1:
times = s // (len(words) - 1)
res = s % (len(words) - 1)
for i in range(1, len(words)):
if res == 0:
ans = ans + ' ' * (times + 1) + words[i]
else:
ans = ans + ' ' * (times + 1 + 1) + words[i]
res -= 1
else:
ans = ans + ' ' * s
return ans
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
Ans = []
i, L = 0, 0
while i < len(words):
if len(words[i]) + i + L <= maxWidth:
if i == len(words) - 1: # 判断是否到达最后一个单词
cur = self.space(words, maxWidth - L - i + 1, True)
cur = cur + ' ' * (maxWidth - len(cur)) # 最后一行后面用空格填满
Ans.append(cur)
return Ans
L = L + len(words[i])
i += 1
else:
cur = self.space(words[:i], maxWidth - L - i + 1, False)
Ans.append(cur)
words = words[i:]
i, L = 0, 0
return Ans别人C++：
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> res;
for(int i = 0, k, l; i < words.size(); i += k) {
for(k = l = 0; i + k < words.size() && l + words[i+k].size() <= maxWidth - k; k++) {//L-k因为每一个单词都有一个空格，l是一行中字符的长度
l += words[i+k].size();
}
string tmp = words[i];
for(int j = 0; j < k - 1; j++) {
if(i + k >= words.size()) tmp += " ";//最后一行，只加一个空格
else tmp += string((maxWidth - l) / (k - 1) + (j < (maxWidth - l) % (k - 1)), ' ');//不是最后一行，补齐空格，最左边(L - l) % (k - 1)个单词后要比之后的多一个空格
tmp += words[i+j+1];
}
tmp += string(maxWidth - tmp.size(), ' ');//最后一行，末尾补空格
res.push_back(tmp);
}
return res;
}
};
转化的python版：
class Solution:
def fullJustify(self,words,maxWidth):
res=[]
i=0
while i< len(words):
k,l=0,0
while i+k<len(words) and (l+len(words[i+k]))<= (maxWidth-k):
l+=len(words[i+k])
k+=1
tmp=words[i]
j=0
while j<k-1:
if i+k>=len(words):
tmp+=' '
else:
tmp+=' '*((maxWidth-l)//(k-1)+(j<(maxWidth-l)%(k-1)))
tmp+=words[i+j+1]
j+=1
tmp+=' '* (maxWidth-len(tmp))
res.append(tmp)
i+=k
return res