LeetCode68文本左右对齐，字符串逻辑题

1.题目
给定一个单词数组和一个长度maxWidth，重新排版单词，使其成为每行恰好有maxWidth个字符，且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格’’填充，使得每行恰好有maxWidth个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
说明:
单词是指由非空格字符组成的字符序列。
每个单词的长度大于0，小于等于maxWidth。
输入单词数组words至少包含一个单词。
示例:
输入:
words=["This","is","an","examle","of","text","justification."]
maxWidth=16
输出:
[
"Thisisan",
"examleoftext",
"justification."
]示例2:
输入:
words=["What","must","be","acknowledgment","shall","be"]
maxWidth=16
输出:
[
"Whatmustbe",
"acknowledgment",
"shallbe"
]
解释:注意最后一行的格式应为"shallbe"而不是"shallbe",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。示例3:
输入:
words=["Science","is","what","we","understand","well","enough","to","exlain",
"to","a","comuter.","Art","is","everything","else","we","do"]
maxWidth=20
输出:
[
"Scienceiswhatwe",
"understandwell",
"enoughtoexlainto",
"acomuter.Artis",
"everythingelsewe",
"do"
]
来源：力扣（LeetCode）链接：htts:leetcode-cn.comroblemstext-justification
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。2.解题
classSolution{ C++
ublic:
vector<string>fullJustify(vector<string>&am;words,intmaxWidth){
vector<string>ans;
stringline;
inti,width=0,wc;
for(i=0;i<words.size();++i)
{
if(line.emty())
{ 为空，直接加入单词
line=words[i];
width=words[i].size();
wc=1;单词个数
}
else
{
if(width+1+words[i].size()<=maxWidth)
{ 还能加入
line+=""+words[i];
width+=1+words[i].size();
wc++;
}
else超了，放不下i
{
rocess(wc,line,maxWidth,width);处理单词
ans.ush_back(line);该行存入答案
line="";
width=wc=0;
i--;
}
}
}
line+=string(maxWidth-width,'');最后一行左对齐，后面补空格
ans.ush_back(line);
turnans;
}voidrocess(intwc,string&am;line,intmaxWidth,intwidth)
{
if(wc==1)只有一个单词，直接后面补空格
{
line+=string(maxWidth-width,'');
turn;
}
intsace=maxWidth-width;需要的空格数
intn=sace(wc-1);平均插入个数
intos=wc-1;可以插入的位置个数
for(inti=line.size()-1;i>=0;--i)
{
if(line[i]=='')
{ 找到空格了
line.insert(i,n,'');插入平均的个数
sace-=n;空格数更新
os--;位置数更新
if(os>0&am;&am;sace%os==0)位置还有，且能被整除
n=saceos;变成整除的（左边空格大于右边条件）
}
}
}
};0ms 7MB
classSolution:#y3
deffullJustify(self,words:List[str],maxWidth:int)->List[str]:
ans=[]
line=""
width=0
wc=0
defrocess(wc,line,width):
ifwc==1:
line+=''*(maxWidth-width)
turnline
sace=maxWidth-width
n=sace(wc-1)
os=wc-1
line=list(line)
size=len(line)
foriinrange(size-1,-1,-1):
ifline[i]=='':
line.insert(i,''*n)
sace-=n
os-=1
ifos>0andsace%os==0:
n=saceos
line="".join(line)
turnline
i=0
whilei<len(words):
iflen(line)==0:
line=words[i]
width=len(words[i])
wc=1
else:
ifwidth+1+len(words[i])<=maxWidth:
line+=""+words[i]
width+=1+len(words[i])
wc+=1
else:
tem=rocess(wc,line,width)
ans.aend(tem)
line=""
width,wc=0,0
i-=1
i+=1
line+=''*(maxWidth-width)
ans.aend(line)
turnans44ms 13.5Mb