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

jerryxjr1220

第四届鱼C论坛精英挑战赛开始咯！为了增加趣味性，本届仍然延续“新玩法”-- “押宝玩法”，“竞猜玩法”和“擂主玩法”。

同时，根据以往鱼油的反馈，精英赛题目普遍偏难，所以参与的鱼油相对较少。为了提高大家的参与度，本届挑战赛会大幅降低难度，使大部分鱼油都能参赛。同时，会增设一、二、三名奖励，第一名奖励50鱼币，第二名30鱼币，第三名20鱼币。

新玩法规则：

1. 押宝玩法：由于押宝玩法参与人数很少，故暂停押宝。后续有改进玩法，会再公布。

2. 竞猜玩法：直接在比赛帖的下方进行投票，凡事“竞赛”获胜者，将奖励5鱼币。竞猜无门槛，人人都可以参与。竞猜以后，请在本帖留个言，方便领取奖励。

3. 擂主玩法：上一期挑战成功的鱼油成为挑战赛的擂主，擂主有优先权提议下一期的赛题，一届挑战赛共分5期，同一届中当擂主最长的鱼油有额外奖励。

本期题目： 下一个包含有相同数字的整数

给定一个正整数m，请输出下一个包含有相同数字的整数n. 如果n不存在，则输出None.
要求: n是由m中的数字经过不同的排序后得到，而且n>m。如果存在k，也是由m中的数字经过不同的排序后得到，而且k>m，则必须满足n<k

求下一个包含有相同数字的整数。

1. def next_int(m):
   
2.     '''your code here'''
   
3.     return n

复制代码

要求： 结果正确，程序效率高，代码简洁

注：给定的m可能会有10位数字或以上，请注意运算效率

截止日期： 12月10日24时

本期擂主： 蓝色王魂  

@小甲鱼 @冬雪雪冬 @～风介～ @SixPy

提供几组测试数据及答案，可以自行对照：
输入m = 24531，输出n = 25134 #因为25134是24531的一个排列，并且25134>24531，并且25134正好是下一个比24531大的不同排列的整数。
输入m = 54321，输出n = None
输入m = 28543211，输出n = 31122458

竞猜：回答正确的参赛者的人数

yjsx86

1. def next_int(m):
   
2.     m = [int(x) for x in str(m)]
   
3.     if m[0] > max(m[1:]):
   
4.         return None
   
5.     temp, i, n, flag = 0, -1, [], True
   
6.     while flag:
   
7.         for j in range(len(n)):
   
8.             if m[i] < n[j]:
   
9.                 temp = n[j]
   
10.                 n[j] = m[i]
    
11.                 n.insert(0,temp)
    
12.                 n = m[:i] + n
    
13.                 flag = False
    
14.                 break
    
15.         if flag:
    
16.             n.append(m[i])
    
17.             i -= 1
    
18.     rs = 0
    
19.     for k in range(len(n)):
    
20.         rs = rs*10 + n[k]
    
21.     return rs

复制代码

Elastcio

1. def next_int(m):
   
2.     m_list = list(map(int,list(str(m))))
   
3.     t_list = [m_list[-1]]
   
4.    
   
5. 
   
6.     for index, item in enumerate(reversed(m_list)):
   
7.         if index:
   
8.             if item >= t_list[0]:
   
9.                 t_list.insert(0,item)
   
10.             else:
    
11.                 m_list[-index-1] = min(x for x in t_list if x > item)
    
12.                 t_list[t_list.index(min(x for x in t_list if x > item))] = item
    
13.                 break
    
14.         if index == len(m_list)-1: return None
    
15.     n = m_list[0:len(m_list)-len(t_list)]+sorted(t_list)
    
16. 
    
17.                
    
18.     return ''.join(list(map(str,n)))
    
19. 
    
20. print(next_int(24531))  #25134
    
21. print(next_int(54321))  #None
    
22. print(next_int(28543211))   #31122458
    
23. print(next_int(4068929357253497956390133846146756840221))   #4068929357253497956390133846146756841022
    
24. 
    
25. 
    

复制代码

赵鑫权2353

单数

土沙拉

1. def next_int(m):
   
2.     list1 = list(str(m))
   
3.     i = len(list1) - 1
   
4.     while i != 0 and list1[i] <= list1[i - 1]:
   
5.         i -= 1
   
6.     if i == 0:
   
7.         return 'None'
   
8.     w=min([list1[x] for x in range(i, len(list1)) if list1[x] > list1[i - 1]])
   
9.     ans = str(m)[:i - 1] + w
   
10.     list1=list1[i-1:]
    
11.     list1.remove(w)
    
12.     list1.sort()
    
13.     for t in list1:
    
14.         ans+=t
    
15.     return int(ans)

复制代码

SylarPu

1. def next_int(m):
   
2.     size=len(m)
   
3.     a=list(m)
   
4.     i=size-2
   
5.     while i>=0 and a[i]>=a[i+1]:
   
6.         i-=1
   
7.     if i<0:
   
8.         return False
   
9.     j=size-1
   
10.     while a[j]<=a[i]:
    
11.         j-=1
    
12.     t=a[i]
    
13.     a[i]=a[j]
    
14.     a[j]=t
    
15.     b=a[i+1:size]
    
16.     b.reverse()
    
17.     a[i+1:size]=b
    
18.     m=''.join(a)
    
19.     return m
    

复制代码

SylarPu

1. def next_int(m):
   
2.     a=list(str(m))
   
3.     size=len(a)
   
4.     i=size-2
   
5.     while i>=0 and a[i]>=a[i+1]:
   
6.         i-=1
   
7.     if i<0:
   
8.         return False
   
9.     j=size-1
   
10.     while a[j]<=a[i]:
    
11.         j-=1
    
12.     t=a[i]
    
13.     a[i]=a[j]
    
14.     a[j]=t
    
15.     b=a[i+1:size]
    
16.     b.reverse()
    
17.     a[i+1:size]=b
    
18.     m=int(''.join(a))
    
19.     return m

复制代码

大月饼

1. def next_int(m):
   
2.     flag = 0
   
3.     nums = list(str(m))
   
4.     for i in range(len(nums)-2,-1,-1):
   
5.         if nums[i]<nums[i+1]:
   
6.             flag = 1
   
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 == 0:
    
18.         return None
    
19.     else:
    
20.         temp=''
    
21.         for i in range(len(nums)):
    
22.             temp=temp+nums[i]
    
23.         n=int(temp)
    
24.     return n

复制代码

cngoodboy

1. def next_int(m):
   
2.     m = list(str(m))
   
3.     l = len(m)
   
4.     for i in range(l-1, 0, -1):
   
5.         if m[i] > m[i-1]:
   
6.             break
   
7.     else:
   
8.         return None
   
9.     mid = i
   
10.     for j in range(l-1, i-1, -1):
    
11.         if m[i-1] < m[j] <= m[i]:
    
12.             if m[mid] > m[j]:
    
13.                 mid = j
    
14.     m[i-1], m[mid] = m[mid], m[i-1]
    
15.     m[i:] = sorted(m[i:])
    
16.     s = ''.join(m)
    
17.     return int(s)
    

复制代码

利用字符串
在我的机子上一次计算大概3微秒，弱机可能5微秒

gunjang

1. #http://bbs.fishc.com/thread-100954-1-1.html
   
2. def next_int(m):
   
3.         m = str(m)
   
4.         if len(m)==1: #one digit
   
5.                 return None
   
6.         for i in range(len(m)-2, -1, -1):
   
7.                 if m[i] < m[i+1]: break
   
8.         if (i==0) and (m[0] >= m[1]): #max number
   
9.                 return None
   
10. 
    
11.         for j in range(len(m)-1, i, -1):
    
12.                 if m[j] > m[i]: break
    
13. 
    
14.         return int(m[:i]+m[j]+m[len(m)-1:j:-1]+m[i]+m[j-1:i:-1])
    
15. 
    
16. #输入m = 28543211，输出n = 31122458
    
17. print(28543211, next_int(28543211))
    
18. #24531 25134
    
19. print(24531, next_int(24531))
    
20. print(54321, next_int(54321))
    
21. print(next_int(3))
    
22. print(4054321, next_int(4054321))       

复制代码

BngThea

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

复制代码

蓝色王魂

1. def next_int(m):
   
2.     list1 = [int(each) for each in str(m)]
   
3.     length = len(list1)
   
4.     for i in range(length-2,-1,-1):
   
5.         if list1[i] < list1[i+1]:
   
6.             n_change = i
   
7.             for j in range(length-1,i,-1):
   
8.                 if list1[j] > list1[i]:
   
9.                     list1[j],list1[i] = list1[i],list1[j]
   
10.                     break
    
11.             break
    
12.     else:
    
13.         return None
    
14.     change = list1[i+1:]
    
15.     change.reverse()
    
16.     list2 =list1[:n_change+1] + change
    
17.     answer = ''
    
18.     for each in list2:
    
19.         answer += str(each)
    
20.     return int(answer)

复制代码

qwc3000

def next_int(m):
    strinputlist = list(str(m))
    tmplist = []
    tmplist.append(strinputlist.pop())
    j = 0
    strmin = 0
    while strmin == 0 and len(strinputlist) != 0:
        tmpstr = strinputlist.pop()
        tmplist.append(tmpstr)
        if tmpstr >= max(tmplist):
            pass
        else:
            i = 0
            tmpmaxlist = []
            while i < len(tmplist):
                if tmpstr < tmplist[i]:
                    tmpmaxlist.append(tmplist[i])
                i += 1
            strmin = min(tmpmaxlist)
    if strmin == 0:
        n=None
    else:
        tmplist.remove(strmin)
        tmplist.sort()
        strinputlist.append(strmin)
        strinputlist.extend(tmplist)
        n=int(''.join(strinputlist))
    return n

print(next_int(54321))
print(next_int(28543211))
print(next_int(24531))
---------------结果------------------
None
31122458
25134

5dzz

666，DDDDDDDDDDDDDDD

万事屋

def next_int(m):
    l,t=list(str(m)),-1
    for i in range(len(l)-1,0,-1):
        if l[i]>l[i-1]:
            t=i-1
            break
    if t==-1:
        n=None
    else:
        for i in range(len(l)-1,0,-1):
            if l[t]<l[i]:
                l[t],l[i]=l[i],l[t]
                n=int(''.join(l[:t+1])+''.join(sorted(l[t+1:])))
                break
    return n

tuifei

def next_int(m):
    '''your code here'''

    a = str(m)
    s = len(a)
    b = int(a)
    try:
        for x in range(2,s+1):
            for c in range(1,x):
                if a[-x] < a[-c]:
                    raise ValueError
                    
    except ValueError:
        e = list(a[0:s-x])
        e.append(a[-c])
        f = list(a[s-x:s-c])+list(a[s-c+1:])
        for i in range(len(f)-1):
            for j in range(len(f) - i -1):
                if f[j] > f[j+1]:
                    f[j], f[j+1] = f[j+1], f[j]
        g = (e+f)
        n = 0
        for h in range(0,s):

            n = n+int(g[h])*10**(s-h-1)
            

    else:
        n = None
    return n

        
            

Ruide

双数 + 1！

拓离

1. 
   
2. def next_int(m):
   
3.     m = str(m)
   
4.     i1 = 0
   
5.     i2 = 0
   
6.     for i in range(len(m)-1, -1, -1):
   
7.         for j in range(i, len(m)):
   
8.             if int(m[j]) > int(m[i]):
   
9.                 i1 = j
   
10.                 i2 = i
    
11.         if i1!=i2:break   
    
12.     if i1 == i2:
    
13.         return None
    
14. 
    
15.     m1 = m[i1+1:][::-1]
    
16.     m2 = m[i2+1:i1][::-1]
    
17.     n = m[:i2]+m[i1]+m1+m[i2]+m2
    
18.     return n
    
19. 
    
20. if __name__ == "__main__":
    
21.     next_int(m)
    

复制代码

            

fengling1017

我刚入门，我猜1，单数

冷笑寒风

1. #python 3.4
   
2. #主要使用数组排序
   
3. def next_int(m):
   
4.     n = 0
   
5.     n_str = ''
   
6.     change_Str = str(m)   #转换成字符串
   
7.     d = []                #用来存放转换数组
   
8.     n_list = []           #最后答案数组
   
9.     for x in range (len(change_Str)):   #获得与m序列相同的数组
   
10.         d.append(change_Str[x])
    
11.     d.reverse ()          #为从后往前判断将数组改为倒序
    
12.     for x in range (len(d)-1):         
    
13.         
    
14.         if(d[x]>d[x+1]):                #两两比大小若发现原数组后一位大于前一位
    
15.                                         #将前一位连同所有后置位所有数取出，选出
    
16.             g=''  #存放选出数字         #比之前前一位大并且最小的一位数
    
17.             e = d[0:x+2] #抽取自数列    #后按照原数组前面不变将选出得数插在后面
    
18.             e.sort()                    #最后把后面的数从小到大排列插在最后
    
19.             index = e.index(d[x+1])+1   #完成 ^V^
    
20.             f = index                   #f存放比前一位大最小的数字
    
21.             for x in range(len(e)):     #这里处理子数列有重复数字情况
    
22.                 if (x<len(e) and e[f]==e[f-1]):
    
23.                     f+=1
    
24.                 elif (x==len(e)):
    
25.                     pass
    
26.                     
    
27.                 else:
    
28.                     break
    
29.             g=e[f]                      #存放选出数字
    
30.             e.remove(e[f])
    
31.             e.reverse()
    
32.             for  x in range (len(e)):   
    
33.                
    
34.                 n_list.append(e[x])
    
35.             n_list.append(g)
    
36.             for x in d[x+2:]:
    
37.                 n_list.append(x)
    
38.             break
    
39. 
    
40.         else:
    
41.             continue
    
42.     if(len(n_list)==0):
    
43.         return None
    
44.             
    
45. 
    
46.     n_list.reverse()
    
47.     for x in n_list:
    
48.         n_str += x
    
49.     n = int(n_str)
    
50.    
    
51.     return n
    

复制代码