Leetcode做题日记：68. 文本左右对齐(PYTHON)

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
1
2
3

示例:

输入:
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 "
]

第一次的代码：
可以说写的很艰难了，首先得到words的所有单词的长度，依次输入到列表alllen中，然后根据每个单词的长度，以及每个单词间最少一个空格这种形式，计算每个maxWidth可以容纳的单词数，并依次储存到列表ans中，接着计算每个maxWidth中需要补全的空格数，并且要求尽可能的均匀，将单词间的空格数计算后储存到列表kklen中，最后就是填写maxWidth了，首先先填写前n-1个，最后填写最后一个maxWidth

	ans=[]
        alllen=[]
        for i in words: #计算每个单词的长度
            alllen.append(len(i))
        i=1
        
        onelen=alllen[0] #计算每个maxWidth能容纳的单词数
        numword=0
        b=0
        while b<len(words):
            while onelen<=maxWidth : #当前单词+空格数小于maxWidth，表示还能加单词
                numword+=1
                if i>len(words)-1:
                    break
                onelen+=alllen[i]+1 #+1因为每个词间空格至少是1
                i=i+1
            i=i-1 #这一步是因为上一个循环i+1的单词没有被计算，先-1表示上一个单词
            onelen=alllen[i]
            i=i+1 #再+1表示下一个要加的单词长度
            ans.append(numword) #记录一次循环maxWidth能容纳的单词数
            b=b+numword
            numword=0 
        
        minans=''  #计算maxWidth内单词间空格列表kklen
        Ans=[]
        jsq=0 #表示当前单词位置
        i=0
        kklen=[]
        while i<len(ans)-1 :
            if ans[i]==1: #如果一个maxWidth只有一个单词，直接右补空格
                minans=words[jsq]+' '*(maxWidth-alllen[jsq])
                Ans.append(minans)
            else: #如果有两个及以上的单词
                klen=maxWidth 
                for j in range(ans[i]):
                    klen-=alllen[jsq+j] #计算除了单词长度能补的空格数
                if klen%(ans[i]-1)==0: #若空格总数能整除单词间隔数
                    for k in range(ans[i]-1):
                        kklen.append(klen//(ans[i]-1))
                else: #若不能整出，则通过循环得到kklen列表，例如3个空格要分配给2个
                #单词间隔，首先分配[1,1]，还剩一个空格，分配给第一个，得到[2,1]
                    
                    for a in range(ans[i]-1): #先将每个单词间隔填写一个空格
                        kklen.append(1)
                    d=0 
                    d1=0
                    while d1<klen-(ans[i]-1): #再将剩余空格单个顺序加入单词间隔
                        kklen[d]+=1
                        d1+=1
                        d+=1
                        if d==len(kklen): #顺序加入一轮后，在开启下一轮+空格
                            d=0       
                

		l=0 #开始填写前n-1个maxWidth
                while l<ans[i]-1:
                    minans+=words[jsq+l]+' '*kklen[l] #读取单词以及间隔空格
                    l+=1
                minans+=words[jsq+l]    
                Ans.append(minans)
            jsq=jsq+ans[i] #更新下一个maxWidth开始的单词位置
            i=i+1
            kklen=[]
            minans=''
        
        endans='' #填写最后一个maxWidth    
        for m in range(ans[i]-1):
            endans+=words[jsq+m]+ ' '
        endans+=words[-1]
        endans+=' '*(maxWidth-len(endans))
        Ans.append(endans)
        return Ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

28ms，排名36%