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

新手·ing

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

def next_int(m):
          if str(m)[0] == max(str(m)):
                    return None
          else:  
                    n = m
                    l1 = [str(x) for x in str(m)]
                    while True:
                              n += 1
                              l2 = [str(y) for y in str(n)]
                              l1.sort()
                              l2.sort()
                              if l2 == l1:
                                        return n
                              else:
                                        continue

大月饼

def next_int(m):
    flag = False
    nums = list(str(m))
    for i in range(len(nums)-2,-1,-1):
        if nums[i] < nums[i+1]:
            flag = True
            temp = nums[i:]
            for j in range(len(temp)-1,-0,-1):
                if temp[0] < temp[j]:
                    t = temp[0]
                    temp[0] = temp[j]
                    temp[j] = t[:]
                    break
            temp[1:] = sorted(temp[1:])
            nums = nums[:i]+temp
            break
    if flag:
        temp = ''
        for i in range(len(nums)):
            temp = temp+nums[i]
        n = int(temp)
    else:
        return None
    return n

shigure_takimi

# 第一种方法只要0.1秒。
def next_int(n):
    if n < 10:
        return None
    else:
        numbers = list(str(n))
        length = len(numbers)
        index = -1  # 确定倒数几位重排即可得到所求的数
        for index1 in range(-1, -length, -1):
            index2 = index1 - 1
            if numbers[index1] > numbers[index2]:
                index = index2
                break
        else:
            return None
        for index1 in range(-1, index,-1): # 重排后几位数
            if numbers[index1] > numbers[index]:
                numbers[index1],numbers[index] = numbers[index],numbers[index1]
                numbers[index+1:] = sorted(numbers[index+1:])
                break
        return ''.join(numbers)


print(next_int(13819483198349138491834918439819481091931))
print(next_int(23))
print(next_int(23457))
print(next_int(192131931938))

##  第二种笨方法。
##  八位数速度还可以，零点几秒，10位数大概4秒，11位数以上不行。


from itertools import permutations

def next_int(n):
        a = sorted(list(permutations(str(n))))
        for i in a:
                if int(''.join(i))>n:
                        return int(''.join(i))
        return None

print(next_int(24531))
print(next_int(54321))
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竹肃

def next_int(m):
    list1 = list(str(m))
    l = len(list1)
    list2 = list1[:]
    list2.sort()
    list3 = list2[:]
    list3.reverse()
    k = 1
    if list3 == list1:
        print('None')
        return
    else:
        while True:
            list1 = list(str(m))
            list2 = list1[0:k]
            list3 = list1[k:l]
            list4 = list3[:]
            list4.sort()
            list5 = list4[:]
            list5.reverse()
            if list3 == list5:
                for i in list4:
                    if i > list2[k-1]:
                        list6 = [i]
                        break
                list7 = list2[:]
                list7.pop()
                list8 = list5[:]
                list8.remove(i)
                list9 = list2[k-1:k] + list8[:]
                list9.sort()
                list10 = list7[:] + list6[:] + list9[:]
                n = ''.join([str(i) for i in list10])
                print(n)
                break
            else:
                k += 1
                continue 
    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万位数。