[已解决]Python：每日一题 253（高额悬赏）

zltzlt

今天的题目：

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

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

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

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

说明：

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

示例 1:

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

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

华一仙

2019-10-7 12:57:47

1. def f253(words, maxWidth):
   
2.     def adjustSpace(lst):
   
3.         string = ""
   
4.         num_lst, len_lst = len(lst), len(''.join(lst))
   
5.         if num_lst == 1:
   
6.             return lst[0] + ' ' * (maxWidth - len_lst)
   
7.         every_space = (maxWidth - len_lst) // (num_lst - 1)
   
8.         surplus =  (maxWidth - len_lst) % (num_lst - 1)
   
9.         for i in range(num_lst - 1):
   
10.             string += lst[i] + ' ' * every_space
    
11.             if surplus:
    
12.                 string += ' '
    
13.                 surplus -= 1
    
14.         return string + lst[-1]
    
15. 
    
16.     def adjustLastLine(lst):
    
17.         if len(lst) == 1:
    
18.             return lst[0] + ' ' * (maxWidth - len(lst[0]))
    
19.         string = ' '.join(lst)
    
20.         return string + ' ' * (maxWidth - len(string))
    
21. 
    
22.     res = []
    
23.     list_tmp, len_list_tmp = [], 0
    
24.     for word in words:
    
25.         len_word = len(word)
    
26.         if len_list_tmp + len_word < maxWidth:
    
27.             list_tmp.append(word)
    
28.             len_list_tmp += len_word + 1
    
29.         elif len_list_tmp + len_word == maxWidth:
    
30.             list_tmp.append(word)
    
31.             res.append(' '.join(list_tmp))
    
32.             list_tmp, len_list_tmp = [], 0
    
33.         else:
    
34.             res.append(adjustSpace(list_tmp))
    
35.             list_tmp, len_list_tmp = [word], len_word + 1
    
36.     if len_list_tmp:
    
37.         res.append(adjustLastLine(list_tmp))
    
38.     return res

复制代码

跳转到最佳答案楼层

华一仙

1. def f253(words, maxWidth):
   
2.     def adjustSpace(lst):
   
3.         string = ""
   
4.         num_lst, len_lst = len(lst), len(''.join(lst))
   
5.         if num_lst == 1:
   
6.             return lst[0] + ' ' * (maxWidth - len_lst)
   
7.         every_space = (maxWidth - len_lst) // (num_lst - 1)
   
8.         surplus =  (maxWidth - len_lst) % (num_lst - 1)
   
9.         for i in range(num_lst - 1):
   
10.             string += lst[i] + ' ' * every_space
    
11.             if surplus:
    
12.                 string += ' '
    
13.                 surplus -= 1
    
14.         return string + lst[-1]
    
15. 
    
16.     def adjustLastLine(lst):
    
17.         if len(lst) == 1:
    
18.             return lst[0] + ' ' * (maxWidth - len(lst[0]))
    
19.         string = ' '.join(lst)
    
20.         return string + ' ' * (maxWidth - len(string))
    
21. 
    
22.     res = []
    
23.     list_tmp, len_list_tmp = [], 0
    
24.     for word in words:
    
25.         len_word = len(word)
    
26.         if len_list_tmp + len_word < maxWidth:
    
27.             list_tmp.append(word)
    
28.             len_list_tmp += len_word + 1
    
29.         elif len_list_tmp + len_word == maxWidth:
    
30.             list_tmp.append(word)
    
31.             res.append(' '.join(list_tmp))
    
32.             list_tmp, len_list_tmp = [], 0
    
33.         else:
    
34.             res.append(adjustSpace(list_tmp))
    
35.             list_tmp, len_list_tmp = [word], len_word + 1
    
36.     if len_list_tmp:
    
37.         res.append(adjustLastLine(list_tmp))
    
38.     return res

复制代码

_2_

>>>彩色的沙发 <<<

_2_

关于算法，我并不是很懂

战场原

def solution(words, maxWidth):
    length = 0
    tmplist = list()
    res = list()
    i = 0
    while i<len(words):
        length += len(words[i])
        if length<=maxWidth:
            tmplist.append(words[i])
            i+=1
            length += 1
        else:
            newlength = 0
            for j in tmplist:
                newlength += len(j)
            tmp = ""
            if len(tmplist) != 1:
                average = (maxWidth-newlength)//(len(tmplist)-1)
                mod = (maxWidth-newlength)%(len(tmplist)-1)
                for j in range(len(tmplist)):
                    if j != len(tmplist)-1:
                        if mod != 0:
                            tmp += (tmplist[j]+" "+" "*average)
                            mod -= 1
                        else:
                            tmp += (tmplist[j]+" "*average)
                    else:
                        tmp+=(tmplist[j])
            else:
                tmp = tmplist[0] + " "*(maxWidth-newlength)
            res.append(tmp)
            length=0
            tmplist = list()
    tmp = ""
    for i in range(len(tmplist)):
        if i != len(tmplist)-1:
            tmp += (tmplist[i]+" ")
        else:
            tmp+=tmplist[i]
    tmp += " "*(maxWidth-len(tmp))
    res.append(tmp)
    return res

# 感觉写了一堆辣鸡...

zltzlt

战场原 发表于 2019-10-7 14:58
def solution(words, maxWidth):
    length = 0
    tmplist = list()

恭喜通过！

执行用时：44 ms

Unicorn#

还赶得上吗
新人来报道
不知题主想要输出列表还是文本，列表的注释掉了，这里是文本的

1. def solve(words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16):
   
2.     length = []
   
3.     res = []
   
4.     for each in words:
   
5.         length.append(len(each))
   
6.     length.append(255)
   
7.     print((maxWidth - 1 - int((maxWidth-1)/2))*' '+'['+int((maxWidth-1)/2)*' ')
   
8.     while len(words) > 0:
   
9.         temp_words = []
   
10.         l = maxWidth
    
11.         counter = -1
    
12.         while l > length[counter+1]:
    
13.             counter += 1
    
14.             l -= length[counter] + 1
    
15.         temp_words = words[:counter+1]
    
16.         del words[:counter+1], length[:counter+1]
    
17.         ans = ''
    
18. 
    
19.         if len(words) == 0 or counter == 0:
    
20.             right = l
    
21.             left = 0
    
22.         else:
    
23.             l += 1
    
24.             right = int(l/2)
    
25.             left = l - right
    
26.             right -= 1
    
27. 
    
28.         ans += ' ' * left
    
29.         for each in temp_words:
    
30.             ans += each + ' '
    
31.         ans += ' ' * right
    
32.         print(ans)
    
33.         #res.append(ans)
    
34.     print((maxWidth - 1 - int((maxWidth-1)/2))*' '+']'+int((maxWidth-1)/2)*' ')
    
35.     #return res

复制代码

XiaoPaiShen

1. class WordFilling:
   
2.     def __init__(self):        
   
3.         self.result = list()
   
4. 
   
5.     def fillout(self, words, max_width):
   
6.         if not words:
   
7.             return self.result
   
8. 
   
9.         words_len, index = len(words), 0
   
10.         row_index, temp_row = 0, list()
    
11.         
    
12.         while index < words_len:            
    
13.             if (row_index + len(words[index])) <= max_width:
    
14.                
    
15.                 row_index += (len(words[index]) + 1)
    
16.                 temp_row.append(words[index])
    
17.                 index += 1               
    
18.                 continue
    
19.             
    
20.             else:               
    
21.                 if len(temp_row) == 1:  # 只有一个单词
    
22.                     suf_space = max_width - len(temp_row[0])
    
23.                     self.result.append('{0}{1}'.format(temp_row[0], ' '*suf_space))
    
24.                 else:
    
25.                     len_words = len(temp_row)
    
26.                     total_space = max_width - row_index + len_words
    
27.                     avg_space = total_space // (len_words - 1)
    
28.                     pre_space = total_space % (len_words - 1)
    
29. 
    
30.                     if pre_space > 0:
    
31.                         temp = (' '*(avg_space + 1)).join(temp_row[:pre_space])
    
32.                         temp += ' '*avg_space + (' '*avg_space).join(temp_row[pre_space:])
    
33.                     else:
    
34.                         temp = (' '*avg_space).join(temp_row)
    
35. 
    
36.                     self.result.append(temp)
    
37. 
    
38.                 temp_row.clear()
    
39.                 row_index = 0
    
40.                                                          
    
41.         temp = ' '.join(temp_row)
    
42.         self.result.append(temp + ' '*(max_width-len(temp_row)))
    
43.         return self.result
    
44. 
    
45. if __name__ == '__main__':
    
46.    
    
47.     wf = WordFilling()
    
48.     words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]
    
49.     maxWidth = 20
    
50.     print(wf.fillout(words, maxWidth))

复制代码

776667

1. def fun253(words,maxWidth):
   
2.    
   
3.     def fun_x(x,maxWidth):
   
4.         temp,width = [],0
   
5.         x = ['%s '%i for i in x]
   
6.         if sum(len(i) for i in x) < maxWidth+1:
   
7.             return x
   
8.         for i in range(len(x)):
   
9.             width += len(x[i])
   
10.             if width > maxWidth+1:
    
11.                 return temp
    
12.             temp.append(x[i])
    
13. 
    
14.     groups,result = [],[]
    
15.     while words:
    
16.         groups.append(fun_x(words,maxWidth))
    
17.         words = words[len(fun_x(words,maxWidth)):]
    
18.     for i in groups:
    
19.         width = sum(len(j) for j in i)
    
20.         intervals = len(i)-1
    
21.         if intervals == 0:
    
22.             i[0] = i[0] + ' '*((maxWidth+1)-width)
    
23.             result.append(i[0][:-1])
    
24.         elif i == groups[-1]:
    
25.             i[-1] = i[-1] + ' '*((maxWidth+1)-width)
    
26.             result.append(''.join(i)[:-1])
    
27.         else:
    
28.             blanks = ' '*(((maxWidth+1)-width)//intervals)
    
29.             remain = ((maxWidth+1)-width)%intervals
    
30.             for j in range(remain):
    
31.                 i[j] += ' '
    
32.             result.append(blanks.join(i)[:-1])
    
33.     return result

复制代码

ypcgamelife

不错。学习

zltzlt

Unicorn# 发表于 2019-10-7 22:51
还赶得上吗
新人来报道
不知题主想要输出列表还是文本，列表的注释掉了，这里是文本的

解答错误，与题目示例不符，答案作废。

zltzlt

XiaoPaiShen 发表于 2019-10-8 00:28

解答错误，答案作废。

输入：words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出：["This    is    an","example of text","justification.               "]
预期结果：["This    is    an","example  of text","justification.  "]

zltzlt

776667 发表于 2019-10-8 17:08

执行出错，答案作废。

输入：words = ["ask","not","what","your","country","can","do","for","you","ask","what","you","can","do","for","your","country"], maxWidth = 16

lucky邪神

没搞懂，看大神们怎么搞
昨天留下脚印今天在办公室试了次

1. def func253(word,maxlen):
   
2.     result1=[]      #每行内容列表
   
3.     result2=[]      #结果
   
4.     length1=0
   
5.     index =0
   
6.     while index in range(len(word)):
   
7.         length1 +=len(word[index])      #将word[index]加入行后，计算长度
   
8.         if length1<=maxlen: #比较每行的长度与maxlen的大小
   
9.             result1.append(word[index]) #将word[index]加入到行
   
10.             length1 +=1         #航内容加入一个字符串后，补加一个空格
    
11.             index +=1
    
12.         else :      #如果加入word[index]后行长度大于maxlen，考虑换行
    
13.             line=length1-len(word[index])
    
14.             lenth=maxlen-line+1    #计算行长度与maxlen的差
    
15.             if len(result1)==1: #如果只有一个元素
    
16.                 ele=result1[0]+' '*lenth
    
17.             else:
    
18.                 ele=' '.join(result1[:-1]) + ' '*(lenth+1) + result1[-1]
    
19.                         
    
20.             result2.append(ele) #把行元素加入到结果列表
    
21.             result1.clear()     #清空行列表
    
22.             length1=0   #行长度归零
    
23.    
    
24.     lenth=maxlen-length1    #计算行长度与maxlen的差
    
25.     ele=' '.join(result1) + ' '*(lenth+1)      
    
26.     result2.append(ele)
    
27.     return result2

复制代码

回国了，时间好紧，这么晚明天还得五点多起床上班

XiaoPaiShen

zltzlt 发表于 2019-10-8 21:21
解答错误，答案作废。

输入：words = ["This", "is", "an", "example", "of", "text", "justification ...

试试下面的代码吧

1. class WordFilling:
   
2.     def __init__(self):        
   
3.         self.result = list()
   
4. 
   
5.     def fillout(self, words, max_width):
   
6.         if not words:
   
7.             return self.result
   
8. 
   
9.         words_len, index = len(words), 0
   
10.         row_index, temp_row = 0, list()
    
11.         
    
12.         while index < words_len:            
    
13.             if (row_index + len(words[index])) <= max_width:
    
14.                
    
15.                 row_index += (len(words[index]) + 1)
    
16.                 temp_row.append(words[index])
    
17.                 index += 1
    
18.                
    
19.                 continue
    
20.             
    
21.             else:               
    
22.                 if len(temp_row) == 1:  # 只有一个单词
    
23.                     suf_space = max_width - len(temp_row[0])
    
24.                     self.result.append('{0}{1}'.format(temp_row[0], ' '*suf_space))                    
    
25.                 else:
    
26.                     len_words = len(temp_row)
    
27.                     total_space = max_width - row_index + len_words
    
28.                     avg_space = total_space // (len_words - 1)
    
29.                     pre_space = total_space % (len_words - 1)
    
30. 
    
31.                     temp = ''
    
32.                     if pre_space > 0:
    
33.                         for word in temp_row[:-1]:
    
34.                             if pre_space > 0:
    
35.                                 temp += word + ' '*(avg_space + 1)
    
36.                                 pre_space -= 1
    
37.                             else:
    
38.                                 temp += word + ' '*(avg_space)
    
39.                         temp += temp_row[-1]
    
40. 
    
41.                     else:
    
42.                         temp = (' '*avg_space).join(temp_row)
    
43. 
    
44.                     self.result.append(temp)
    
45. 
    
46.                 temp_row.clear()
    
47.                 row_index = 0
    
48.                                                          
    
49.         temp = ' '.join(temp_row)
    
50.         self.result.append(temp + ' '*(max_width-len(temp)))
    
51.         return self.result
    
52. 
    
53. if __name__ == '__main__':
    
54.    
    
55.     wf = WordFilling()
    
56.     words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]
    
57.     # words =  ["This", "is", "an", "example", "of", "text", "justification."]
    
58.     maxWidth = 16
    
59.     print(wf.fillout(words, maxWidth))

复制代码

华博文

1. #在此处设置words值
   
2. words = ["ask","not","what","your","country","can","do","for","you","ask","what","you","can","do","for","your","country"]
   
3. maxWIDTH = 10
   
4. 
   
5. 
   
6. pan = [each for each in words if len(each) > maxWIDTH]
   
7. if not pan:
   
8.     lis = list()
   
9.     chu = list()
   
10.     kong = " "
    
11. 
    
12.     def qu(words , maxWIDTH , lis):
    
13.         num = 0
    
14.         print("len(words)  {}".format(len(words)))
    
15.         for each in range(len(words)):
    
16.             ding = each
    
17.             num += len(words[each]) + 1
    
18.             print("加到{}长度是{}\n".format(words[each]  , num))
    
19.             if num > maxWIDTH and num - 1 != maxWIDTH:
    
20.                 if words[0 : ding]:
    
21.                     lis.append(words[0 : ding])
    
22.                     words = words[ding : ]
    
23.                     return qu(words , maxWIDTH , lis)
    
24.                 else:
    
25.                     pass
    
26.             print(words[each] + " " + words[-1])
    
27.             print(str(words.index(words[each])) + " " + str(len(words) - 1))
    
28.             if words[each] == words[-1] and each == len(words) - 1:  
    
29.                 lis.append(words[:])
    
30.         return lis
    
31.       
    
32.     hou = qu(words , maxWIDTH , lis)
    
33.     for each in range(len(hou)):
    
34.         if len(hou[each]) > 1:
    
35.             text = ""
    
36.             xu = maxWIDTH - ((sum([len(each) for each in hou[each]]) + len(hou[each]) - 1))
    
37.             mei = xu // (len(hou[each]) - 1)
    
38.             yu = xu % (len(hou[each]) - 1)
    
39.             if hou[each] == hou[-1]:
    
40.                 for de in range(len(hou[each])):
    
41.                     text += hou[each][de] + kong
    
42.                 text += kong * xu
    
43.                 chu.append(text)
    
44.             else:
    
45.                 for de in range(len(hou[each]) - 1):
    
46.                     text += hou[each][de] + (kong * mei) + kong
    
47.                     if yu:
    
48.                         text += kong
    
49.                         yu -= 1
    
50.                 text += hou[each][-1]
    
51.                 chu.append(text)
    
52.         else:
    
53.             text = ""
    
54.             xu = maxWIDTH - (sum([len(each) for each in hou[each]]))
    
55.             text += hou[each][0] + (kong * xu)
    
56.             chu.append(text)
    
57.             
    
58.     print("输出结果为：")
    
59.     for each in chu:
    
60.         print(each)
    
61. 
    
62.     print("列表形式：\n{}".format(chu))
    
63. else:
    
64.     print("您输入的值中有超过规定长度的单词~~")
    

复制代码

Unicorn#

重新提交......
题主您没说清楚， 我把正确的给注释掉了
重发

1. def solve(words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16):
   
2.     length = []
   
3.     res = []
   
4.     for each in words:
   
5.         length.append(len(each))
   
6.     length.append(255)
   
7.     while len(words) > 0:
   
8.         temp_words = []
   
9.         l = maxWidth
   
10.         counter = -1
    
11.         while l > length[counter+1]:
    
12.             counter += 1
    
13.             l -= length[counter] + 1
    
14.         temp_words = words[:counter+1]
    
15.         del words[:counter+1], length[:counter+1]
    
16.         ans = ''
    
17. 
    
18.         if len(words) == 0 or counter == 0:
    
19.             right = l
    
20.             left = 0
    
21.         else:
    
22.             l += 1
    
23.             right = int(l/2)
    
24.             left = l - right
    
25.             right -= 1
    
26. 
    
27.         ans += ' ' * left
    
28.         for each in temp_words:
    
29.             ans += each + ' '
    
30.         ans += ' ' * right
    
31.         res.append(ans)
    
32.     return res

复制代码

danteer

1. def func1(words,maxwidth):
   
2.     print((int(maxwidth / 2) - 1) * ' ' + '[' + int(maxwidth/2) * ' ')
   
3.     wordss = []
   
4.     for each in words:
   
5.         wordss.append(each)
   
6.     while len(wordss) > 0:
   
7.         length = 0
   
8.         temp_word = []
   
9.         counter = 0
   
10.         for i in wordss:
    
11.             length += len(i)
    
12.             counter += 1
    
13.             if length >= maxwidth:
    
14.                 break
    
15.             else:
    
16.                 length += 1
    
17.         if length == maxwidth:
    
18.             for k in wordss[:counter]:
    
19.                 temp_word.append(k)
    
20.             del wordss[:counter]
    
21.             str1 = ''
    
22.             for l in temp_word:
    
23.                 str1 += l + ' '
    
24.             str1 = str1.rstrip()
    
25.             print(str1)
    
26.         elif length > maxwidth:
    
27.             for j in wordss[:counter - 1]:
    
28.                 temp_word.append(j)
    
29.             real_length = length - len(wordss[counter - 1]) - counter + 1
    
30.             del wordss[:counter - 1]
    
31.             str1 = ''
    
32.             if len(temp_word) == 1:
    
33.                 str1 += temp_word[0] + (maxwidth - len(temp_word[0])) * ' '
    
34.             else:   
    
35.                 for each in temp_word:
    
36.                     str1 += each + ((maxwidth - real_length) // (len(temp_word) - 1)) * ' '
    
37.                 str1 = str1.rstrip()
    
38.                 if len(str1) < maxwidth:
    
39.                     str1 = str1[:len(temp_word[0])] + (maxwidth - len(str1)) * ' ' + str1[len(temp_word[0]):]   
    
40.             print(str1)            
    
41.         elif length < maxwidth:
    
42.             for each in wordss:
    
43.                 temp_word.append(each)
    
44.             del wordss[:]
    
45.             str1 = ''
    
46.             for each in temp_word:
    
47.                 str1 += each + ' '
    
48.             str1 += (maxwidth - len(str1)) * ' '
    
49.             print(str1)            
    
50.     print((int(maxwidth / 2) - 1) * ' ' + ']' + int(maxwidth/2) * ' ')

复制代码

x287208793

只能写到分割，后面加空格排序怎么都不会

1. def the_words(words,maxwidth):
   
2.     new_words = []
   
3.     while words:
   
4.         sum = 0
   
5.         for each in words:   #遍历words列表中的每个元素
   
6.             sum += len(each) +1   #获取每个元素的累加后的字符长度，每个字符加上一个空格['this is an ']
   
7.             if sum > maxwidth:    #如果遍历累加后的长度大于分割长度maxwidth
   
8.                 new_words.append(' '.join(words[0:words.index(each)]))
   
9.                 words = words[words.index(each):]
   
10.                 break
    
11.             elif sum == maxwidth:
    
12.                 new_words.append(' '.join(words[0:(words.index(each) + 1)]))
    
13.                 words = words[(words.index(each) + 1):]
    
14.                 break
    
15.             elif sum < maxwidth and len(' '.join(words) ) < maxwidth:
    
16.                 new_words.append(' '.join(words))
    
17.                 words = []
    
18.                 break
    
19.     print(new_words)
    
20. 
    
21. 
    
22. words =  ["This", "is", "an", "example", "of", "text", "justification."]
    
23. maxwidth = 16
    
24. 
    
25. the_words(words,maxwidth)
    

复制代码

C驴

关于算法，我并不是很懂