鱼C论坛Python精英挑战赛（第四季03期）

新手·ing

加上numba，不然就不要尝试十位数了......

1. def next_int(m):
   
2.           if str(m)[0] == max(str(m)):
   
3.                     return None
   
4.           else:  
   
5.                     n = m
   
6.                     l1 = [str(x) for x in str(m)]
   
7.                     while True:
   
8.                               n += 1
   
9.                               l2 = [str(y) for y in str(n)]
   
10.                               l1.sort()
    
11.                               l2.sort()
    
12.                               if l2 == l1:
    
13.                                         return n
    
14.                               else:
    
15.                                         continue

复制代码

大月饼

1. def next_int(m):
   
2.     flag = False
   
3.     nums = list(str(m))
   
4.     for i in range(len(nums)-2,-1,-1):
   
5.         if nums[i] < nums[i+1]:
   
6.             flag = True
   
7.             temp = nums[i:]
   
8.             for j in range(len(temp)-1,-0,-1):
   
9.                 if temp[0] < temp[j]:
   
10.                     t = temp[0]
    
11.                     temp[0] = temp[j]
    
12.                     temp[j] = t[:]
    
13.                     break
    
14.             temp[1:] = sorted(temp[1:])
    
15.             nums = nums[:i]+temp
    
16.             break
    
17.     if flag:
    
18.         temp = ''
    
19.         for i in range(len(nums)):
    
20.             temp = temp+nums[i]
    
21.         n = int(temp)
    
22.     else:
    
23.         return None
    
24.     return n

复制代码

shigure_takimi

1. # 第一种方法只要0.1秒。
   
2. def next_int(n):
   
3.     if n < 10:
   
4.         return None
   
5.     else:
   
6.         numbers = list(str(n))
   
7.         length = len(numbers)
   
8.         index = -1  # 确定倒数几位重排即可得到所求的数
   
9.         for index1 in range(-1, -length, -1):
   
10.             index2 = index1 - 1
    
11.             if numbers[index1] > numbers[index2]:
    
12.                 index = index2
    
13.                 break
    
14.         else:
    
15.             return None
    
16.         for index1 in range(-1, index,-1): # 重排后几位数
    
17.             if numbers[index1] > numbers[index]:
    
18.                 numbers[index1],numbers[index] = numbers[index],numbers[index1]
    
19.                 numbers[index+1:] = sorted(numbers[index+1:])
    
20.                 break
    
21.         return ''.join(numbers)
    
22. 
    
23. 
    
24. print(next_int(13819483198349138491834918439819481091931))
    
25. print(next_int(23))
    
26. print(next_int(23457))
    
27. print(next_int(192131931938))

复制代码

1. ##  第二种笨方法。
   
2. ##  八位数速度还可以，零点几秒，10位数大概4秒，11位数以上不行。
   
3. 
   
4. 
   
5. from itertools import permutations
   
6. 
   
7. def next_int(n):
   
8.         a = sorted(list(permutations(str(n))))
   
9.         for i in a:
   
10.                 if int(''.join(i))>n:
    
11.                         return int(''.join(i))
    
12.         return None
    
13. 
    
14. print(next_int(24531))
    
15. print(next_int(54321))
    
16. print(next_int(28543211))

复制代码

shigure_takimi

shigure_takimi 发表于 2017-12-10 22:02

0.01秒都不要，这次对自己的思路还是挺自信的。
希望能进前三。

gunjang

gunjang 发表于 2017-12-8 12:27

晕，10万位，那直接用二分查找了

mmdn

def next_int(m):
    m = [int(x) for x in str(m)]
    if m[0] > max(m[1:]):
        return None
    temp, i, n, flag = 0, -1, [], True
    while flag:
        for j in range(len(n)):
            if m[i] < n[j]:
                temp = n[j]
                n[j] = m[i]
                n.insert(0,temp)
                n = m[:i] + n
                flag = False
                break
        if flag:
            n.append(m[i])
            i -= 1
    rs = 0
    for k in range(len(n)):
        rs = rs*10 + n[k]
    return rs

timeislife

单数还是双数？

万事屋

老哥，我发现好多0.25s的，我能重写一个程序吗?

万事屋

def next_int(m):
    l,t,count=str(m),-1,['','','','','','','','','','']
    for i in range(len(l)-1,0,-1):
        count[int(l[i])]+=l[i]
        if l[i]>l[i-1]:
            t=i-1
            count[int(l[t])]+=l[t]
            num=int(l[t])+1
            break
    if t==-1:
        n=None
    else:
        while count[num]=='':
            num+=1
        n=l[0:t]+str(num)
        count[num]=count[num][1:len(count[num])]
        for i in range(10):
            n=n+count[i]
        n=int(n)
    return n

万事屋

gunjang 发表于 2017-12-11 11:05
晕，10万位，那直接用二分查找了

哇。。大神大神。。。。膜拜膜拜。。。为啥我没想清楚还比你多用了个sort方法也跑进了0.25s啊。。。

万事屋

gunjang 发表于 2017-12-11 11:05
晕，10万位，那直接用二分查找了

其实第二个for循环不用二分查找优化也行啊，第一次for循环的时候先判断相邻位置是否相等，再嵌套一重判断记录降序升序的位置，也就多存最多10个位置，最后再从这10个位置里找就行了，时间上应该会比2分查找快毕竟10<log2,100000，主要是代码难度也低很多

gunjang

万事屋 发表于 2017-12-12 00:08
其实第二个for循环不用二分查找优化也行啊，第一次for循环的时候先判断相邻位置是否相等，再嵌套一重判断 ...

那个增加了复杂性，直接用二分查找，10w位最多17次而已

Bill888

yjsx86 发表于 2017-12-6 16:30

这个代码有问题吧，91234返回怎么会是None，第三第四行判断错了

shawn竹肃

请教一下，如何测试10万位测试运算时间

jerryxjr1220

shawn竹肃 发表于 2017-12-13 13:58
请教一下，如何测试10万位测试运算时间

生成一个10万位的整数就行了啊

shawn竹肃

1. def next_int(m):
   
2.     list1 = list(str(m))
   
3.     l = len(list1)
   
4.     list2 = list1[:]
   
5.     list2.sort()
   
6.     list3 = list2[:]
   
7.     list3.reverse()
   
8.     k = 1
   
9.     if list3 == list1:
   
10.         print('None')
    
11.         return
    
12.     else:
    
13.         while True:
    
14.             list1 = list(str(m))
    
15.             list2 = list1[0:k]
    
16.             list3 = list1[k:l]
    
17.             list4 = list3[:]
    
18.             list4.sort()
    
19.             list5 = list4[:]
    
20.             list5.reverse()
    
21.             if list3 == list5:
    
22.                 for i in list4:
    
23.                     if i > list2[k-1]:
    
24.                         list6 = [i]
    
25.                         break
    
26.                 list7 = list2[:]
    
27.                 list7.pop()
    
28.                 list8 = list5[:]
    
29.                 list8.remove(i)
    
30.                 list9 = list2[k-1:k] + list8[:]
    
31.                 list9.sort()
    
32.                 list10 = list7[:] + list6[:] + list9[:]
    
33.                 n = ''.join([str(i) for i in list10])
    
34.                 print(n)
    
35.                 break
    
36.             else:
    
37.                 k += 1
    
38.                 continue
    
39.     return n
    

复制代码

小白刚学到19课，所以也不清楚怎么测试时间，是要编写一个测试时间的函数么？

shawn竹肃

jerryxjr1220 发表于 2017-12-13 15:08
生成一个10万位的整数就行了啊

自己编写了一个答案发在36楼了（line33的n为什么没有print的话函数运行后return不出来得数，感觉不太理解return在函数里的用法）……

因为小白一枚也不太清楚是怎么得到那个时间（秒数）的，是要编写一个计算时间的函数么？

jerryxjr1220

shawn竹肃 发表于 2017-12-13 15:59
自己编写了一个答案发在36楼了（line33的n为什么没有print的话函数运行后return不出来得数，感觉不太理解 ...

不需要那么复杂，计算时间可以用timeit工具，简单的也可以直接用time库完成。
自己网上搜一下，很多教程的。

shawn竹肃

jerryxjr1220 发表于 2017-12-13 16:54
不需要那么复杂，计算时间可以用timeit工具，简单的也可以直接用time库完成。
自己网上搜一下，很多教程 ...

哦好的，多谢，ps:生成一个10万位的整数，应该是指10^5数量级的整数？还是说函数运行10万次的结果？

jerryxjr1220

shawn竹肃 发表于 2017-12-14 08:13
哦好的，多谢，ps:生成一个10万位的整数，应该是指10^5数量级的整数？还是说函数运行10万次的结果？

10^5 = 100000, 这是5位数的整数。
10^100000才是10万位数。