[已解决]Python：每日一题 284

zltzlt

今天的题目：

给出一组非负整数，重新排列它们的顺序，把它们组成一个最大的整数。

示例 1：

输入：[1, 20, 23, 4, 8]
输出：8423201

示例 2:

输入：[4, 6, 65]
输出：6654

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Unicorn#

2019-12-4 22:37:01

def solve(nums):
    class CapStr(str):
        def __lt__(self, value):
            i = j = 0
            while self[i] == value[j]:
                if i < len(self)-1:
                    i += 1
                if j < len(value)-1:
                    j += 1
                if i == len(self)-1 and j == len(value)-1:
                    break
            return self[i] < value[j]
    return int(''.join(sorted(map(lambda x:CapStr(x), nums), reverse=True)))

跳转到最佳答案楼层

冬雪雪冬

def fun(lst):
    lst.sort(key = lambda x: str(x) + "A", reverse = True)
    return int(''.join(map(str, lst)))
print(fun(lst))

fan1993423

冬雪雪冬 发表于 2019-12-4 21:56

如果是[4,6,67]答案应该是6764

冬雪雪冬

fan1993423 发表于 2019-12-4 22:00
如果是[4,6,67]答案应该是6764

是的，我没考虑周全

冬雪雪冬

再修改一个：

def fun(lst):
    lst.sort(key = lambda x: str(x) + str(x)[-1], reverse = True)
    return int(''.join(map(str, lst)))
print(fun(lst))

Unicorn#

def solve(nums):
    class CapStr(str):
        def __lt__(self, value):
            i = j = 0
            while self[i] == value[j]:
                if i < len(self)-1:
                    i += 1
                if j < len(value)-1:
                    j += 1
                if i == len(self)-1 and j == len(value)-1:
                    break
            return self[i] < value[j]
    return int(''.join(sorted(map(lambda x:CapStr(x), nums), reverse=True)))

阴阳神万物主

我来玩玩，看看有没有我没想到的缺陷。

def solve(nums:list)->int:
    for i in range(len(nums)-1):
        for j in range(i+1,len(nums)):
            a,b = str(nums[i]),str(nums[j])
            if int(a+b) < int(b+a):
                nums[i],nums[j] = nums[j],nums[i]
    #return nums #这是自己调试用的
    res = ''
    for each in nums:
        res += str(each)
    return res

if __name__ == '__main__':
    print('示例1 8423201 输出：',solve([1,20,23,4,8]))
    print('示例1 6654 输出：',solve([4,6,65]))
    print('自测 6664 输出：',solve([66,4,6]))
    print('自测 输出：',solve([21,22,23,24,25,26,22]))

时间复杂度应该是O(n+0.5(n+n^2)) n为列表长度

_谪仙

冬雪雪冬 发表于 2019-12-4 22:17
再修改一个：

对于[2,221]得出结果为2212

阴阳神万物主

冬雪雪冬 发表于 2019-12-4 22:17
再修改一个：

版主大大，这个数据：[262,242,29,282,2822]
试去吧。
我的结果是：
292822822262242
跟我楼上一个道理

冬雪雪冬

感谢楼上两位的提醒。再次修改：

def fun(lst):
    len1 = len(str(max(lst)))
    lst2 = [(str(x), str(x) + str(x)[-1] * (len1 - len(str(x)))) for x in lst]
    lst2.sort(key = lambda x: x[1], reverse = True)
    return int(''.join(map(lambda x: x[0], lst2)))
print(fun(lst))

阴阳神万物主

冬雪雪冬 发表于 2019-12-4 23:31
感谢楼上两位的提醒。再次修改：

我那个数据，输入数据的最后两位交换一下，您这还是错的呢

from 我的 import *
from 冬雪雪冬 import *

lst = [262,242,29,2822,282]
a = fun(lst)
b = solve(lst)
print(b)
print(int(a)-b)

结果：

292822822262242
-540000000
>>> 

hrp

def func284(testlist):
    list1, list2, list3 = [], [], []
    for i in testlist:
        list1.append(len(str(i)))
    maxlength = max(list1)
    list1.clear()
    for i in testlist:
        list1.append(f'{i:{chr(0)}<{maxlength}}')
    list1.sort(reverse=True)
    for i in list1:
        list2.append(i.replace(chr(0), ''))
    num = len(list2)
    maxnum = 1
    while num:
        maxnum *= num
        num -= 1
    while maxnum:
        list3.append(''.join(str(i) for i in list2))
        for i in range(len(list2) - 1):
            if int(list2[i] + list2[i + 1]) < int(list2[i + 1] + list2[i]):
                list2[i], list2[i + 1] = list2[i + 1], list2[i]
            list3.append(''.join(str(i) for i in list2))
        maxnum -= 1
    return int(max(list3))


#testlist = [1, 20, 23, 4, 8]                   # 8,4,23,20,1
#testlist = [4, 6, 65]                          # 6,65,4
#testlist = [262,242,29,2822,282]               # 29,282,2822,262,242
#testlist = [856, 22, 222, 2221, 2223]          # 856,2223,222,22,2221
testlist = [650, 580, 66, 9, 661, 66105, 59]    # 9,66,661,66105,650,59,580

print(func284(testlist))

四点好

冬雪雪冬 发表于 2019-12-4 23:31
感谢楼上两位的提醒。再次修改：

In [9]: def fun(lst):
   ...:     len1 = len(str(max(lst)))
   ...:     lst2 = [(str(x), str(x) + str(x)[-1] * (len1 - len(str(x)))) for x in lst]
   ...:     lst2.sort(key = lambda x: x[1], reverse = True)
   ...:     return int(''.join(map(lambda x: x[0], lst2)))
   ...: print(fun([1,12,123]))                                                                                
123121

答案，不对，我觉的这个题目要用递归做，但递归真的不是我的菜。

四点好

hrp 发表于 2019-12-5 00:20

新版的字符串格式化用的厉害。

hrp

四点好 发表于 2019-12-5 03:25
新版的字符串格式化用的厉害。

我自己又发现BUG了，重新修改了下

四点好

hrp 发表于 2019-12-5 03:39
我自己又发现BUG了，重新修改了下

大晚上这么又激情，我稍微想了一下就放弃，本来想递归做，还是你这种补全的方式相对好理解。

hrp

四点好 发表于 2019-12-5 04:13
大晚上这么又激情，我稍微想了一下就放弃，本来想递归做，还是你这种补全的方式相对好理解。

最近都是昼伏夜出，反正没事做就想一下题
本来我也想做递归的，奈何做不来，就剑走偏锋了

Lamotu

def app(num_list):
    '''给出一组非负整数，重新排列它们的顺序，把它们组成一个最大的整数。
'''
    new_list = []
    new_str = ''
    for i in num_list:
        new_list.append(str(i))
    a=sorted(new_list,key=lambda lists: (lists[0],lists[-1]),reverse=True)
    for x in a:
        new_str+=x
    new_num = int(new_str)
    print(new_num)
if __name__ == '__main__':
  a = [1, 20, 23, 4, 8]
  app(a)
  b = [4, 6, 65]
  app(b)
  c = [2,221]
  app(c)

danteer

def func(list1):
    result = ''
    
    def max1(list1):
        temp = list1[0]
        for i in range(1,len(list1)):
            flag = False
            for j in range(min(len(str(temp)),len(str(list1[i])))):
                if str(temp)[j] > str(list1[i])[j]:
                    flag = True
                    break
                elif str(temp)[j] < str(list1[i])[j]:
                    flag = True
                    temp = list1[i]
                    break
                else:
                    pass
            if flag == False:
                if len(str(temp)) == len(str(list1[i])):
                    pass
                else:
                    list2 = list1.copy()
                    if len(str(temp)) > len(str(list1[i])):
                        x = int(str(temp)[len(str(list1[i])):])
                        list2.remove(temp)
                        list2.append(x)
                        temp2 = max1(list2)
                        if temp2 != x:
                            temp = list1[i] 
                    else:
                        x = int(str(list1[i])[len(str(temp)):])
                        list2.remove(list1[i])
                        list2.append(x)
                        temp2 = max1(list2)
                        if temp2 == x:
                            temp = list1[i]
        return temp
    
    while (len(list1)>0):
        temp = max1(list1)
        result += str(temp)
        list1.remove(temp)
    
    return int(result)

用了递归就没法解决稍微大一点的列表了。。。。。。

danteer

hrp 发表于 2019-12-5 00:20

这函数是一次性的嘛