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

Unicorn#

来了
思路来自以前学排列组合时发现的逆序对规律

这种方法泛用性很强，用于：查找一个组合在全排列中的位置 和 用全排列中的位置找到一个组合
①题中的十进制可以换成任意进制，甚至其他数据类型
②这种思路还可以解决 比这个数小的中第二大的数、第三大的数，比这个数大的第1134个数....这样的问题

加了注释，因为这个思路实在难懂

1. def solve(s):
   
2.     s = list(map(lambda x:int(x), str(s)))
   
3.     n = len(s)
   
4. 
   
5.     #units：单位数列units[i] = i!
   
6.     #代表i位元素的全排列数
   
7.     units = [1]
   
8.     for i in range(1, n):
   
9.         units.append(i*units[-1])
   
10.     units.reverse()
    
11. 
    
12.     #进制转换函数（正向）
    
13.     #由10进制数转换为 用逆序对数表示的新数（新索引）：new_num
    
14.     #逆序对：在数列a中，每一对后项比前向小的数对组成一对逆序对
    
15.     #new_num 由每一位 与其后元素 能组成逆序对的对数组成
    
16.     #如 513 -> [5, 1, 3] -> [(5>1, 5>3), None, None] -> [2, 0, 0]
    
17.     #记 所有原有元素全排列 按有小到大顺序 组成集合为 M
    
18.     #new_num 点乘 units 就能得到原数s在M中的索引值
    
19.     def numeration_transformer(num):
    
20.         index = 0
    
21.         for i in range(n):
    
22.             for j in range(i+1, n):
    
23.                 if num[i] > num[j]:
    
24.                     index += units[i]
    
25.         return index
    
26. 
    
27.     new_index = numeration_transformer(s)
    
28. 
    
29.     if new_index == 0:
    
30.         return -1
    
31.    
    
32.     next_index = new_index - 1
    
33. 
    
34.     #这里不再需要原数s，把它修改为所有元素的顺序排列，以便查找
    
35.     s.sort()
    
36. 
    
37.     #进制转换函数（逆向）
    
38.     def anti_numeration_transformer(index):
    
39.         #首先找到index对应的new_num
    
40.         new_num = []
    
41.         for unit in units:
    
42.             new_num.append(index//unit)
    
43.             index %= unit
    
44.         num = [0]*n
    
45.         #由new_num还原num
    
46.         #观察到这样一个规律，num[i] = s[new_num[i]]
    
47.         #原理：从最高位起，除自己外所有元素都会排在自己后面，所以
    
48.         #      其他任何一个比它小的元素都一定会与它形成逆序对，也
    
49.         #      就是说，它的逆序对数刚好就对应它在有序元素集s中的索
    
50.         #      引。依次类推
    
51.         for i in range(n):
    
52.             num[i] = s[new_num[i]]
    
53.             del s[new_num[i]]
    
54.         return num
    
55. 
    
56.     res_s = anti_numeration_transformer(next_index)
    
57. 
    
58.     #如果0在首位，这个数不合要求。且在它之后的每一个数都会一定以0为首
    
59.     if res_s[0] == 0:
    
60.         return -1
    
61.    
    
62.     res = int(''.join(map(lambda x:str(x), res_s)))
    
63.     return res

复制代码

又找到一种思路，简单暴力但只局限于这道题

1. def solve(s):
   
2.     s = list(map(lambda x:int(x), str(s)))
   
3.     n = len(s)
   
4. 
   
5.     p = -1
   
6.     for i in range(n-2, -1, -1):
   
7.         if s[i] > s[i+1]:
   
8.             p = i
   
9.             break
   
10. 
    
11.     if p == -1:
    
12.         return -1
    
13.    
    
14.     res = [0]*n
    
15.     res[:p] = s[:p]
    
16.     temp = s[p:]
    
17.     temp.sort()
    
18. 
    
19.     t = temp.index(s[p])
    
20.     head = temp.pop(t-1)
    
21.     temp.reverse()
    
22.     temp = [head] + temp
    
23.     res = s[:p] + temp
    
24.     return int(''.join(map(lambda x:str(x), res))) if res[0] != 0 else -1

复制代码

zltzlt

都淡忘 发表于 2019-11-23 20:50
我改变了一下思路，从末位开始考虑，用字典哈希会不会快一点

大数据不能通过

zltzlt

__mrsq__ 发表于 2019-11-23 21:00
我又来了，不好意思，发现有个地方不小心写反了

随机数据不能通过

zltzlt

fish_b 发表于 2019-11-23 21:34

大数据不能通过

archlzy

1. def fun279(num):
   
2.     l = [int(i) for i in str(num)]
   
3.     res = []
   
4.     for i in range(1,len(l)+1): # 倒着依次数
   
5.         if i == 1:       # 第一项跳过
   
6.             pass
   
7.         elif l[-i] < l[-(i-1)]:     # 计算该项与后一项的大小，如果该项小于后一项 跳过
   
8.             pass
   
9.         else:   # 该项大于后一项，而且之前还没有触发跳出，则找到了解 后面写的比较丑
   
10.             temp = l[-i+1:]
    
11.             for j in range(1,i):
    
12.                 if temp[-j] < l[-i]:
    
13.                     t1 = temp.pop(-j)
    
14.                     if t1==0 and i ==len(l):
    
15.                         return -1
    
16.                     temp.append(l[-i])
    
17.                     temp.sort(reverse=True)
    
18.                     res = l[:-i] + [t1] +temp
    
19.                     res = [str(i) for i in res]
    
20.                     return int(''.join(res))
    
21.         if i == len(l):           #如果都数到头了 那说明不行
    
22.             return -1

复制代码

fish_b

1. 
   
2. 
   
3. def f279(n):
   
4.     result=-1
   
5.     if n:
   
6.         list_n=list(map(lambda x: int(x), list(str(n))))
   
7.         i=len(list_n)-2
   
8.         j=i+1
   
9.         max_n=max(list_n)
   
10.         copy=list_n[:]
    
11.         while i<j and j>0:
    
12.             j_num=list_n[j]
    
13.             if j_num==max_n:
    
14.                 j-=1
    
15.                 i=j-1
    
16.                 max_n=list_n[:j]
    
17.                 continue
    
18.             if i == -1:
    
19.                 j-=1
    
20.                 i=j-1
    
21.                 continue
    
22.             if list_n[i]>j_num:
    
23.                 list_n[i],list_n[j] = j_num,list_n[i]
    
24.                 exchange=list_n[i+1:]
    
25.                 exchange.sort(reverse=True)
    
26.                 list_n[i + 1:]=exchange
    
27.                 break
    
28.             else:
    
29.                 i-=1
    
30. 
    
31.         if copy!=list_n and list_n[0]!=0:
    
32.             result=''.join(list(map(lambda x: str(x), list_n)))
    
33.     return int(result)
    

复制代码

zltzlt

Unicorn# 发表于 2019-11-23 21:47
来了
思路来自以前学排列组合时发现的逆序对规律

恭喜通过！

执行用时：897 ms

zltzlt

archlzy 发表于 2019-11-23 21:56

解答错误

输入：10
输出：1
预期结果：-1

zltzlt

fish_b 发表于 2019-11-23 22:13

解答错误

输入：971179
输出：799711
预期结果：919771

零0℃度

1. def f279(num):
   
2.     A = list(str(num))
   
3.     B = list(str(num))
   
4.     n = len(A)
   
5.     for i in range(n - 1, 0, -1):
   
6.         if A[i - 1] > A[i]:
   
7.             j = n - 1
   
8.             while A[j] >= A[i - 1] or A[j] == A[j - 1]:
   
9.                 j -= 1
   
10.             A[j], A[i - 1] = A[i - 1], A[j]
    
11.             break
    
12.     print(A,B)
    
13.     if A == B or A[0] == '0':
    
14.         return -1
    
15.     else:
    
16.         return int(''.join(A))

复制代码

Stubborn

1. def max_nums(n: int) -> int:
   
2.     """
   
3.     在条件允许的情况下，最大的数总是希望向前靠
   
4.     971179  -> left=7 right=1 出现可以交换的时候，
   
5.         其实最希望是在7后面的位置，找一个最接近7的数来进行替换。
   
6.         同时把7后面的数，进行排列出一个最大的数
   
7.     """
   
8.     string = str(n)
   
9.     length = len(string)
   
10.     stick = []
    
11.     for left,right in zip(range(length-2, -1, -1), range(length-1, -1, -1)):
    
12.         if string[left] <= string[right]:
    
13.             stick.append(string[right])
    
14.         else:
    
15.             stick.append(string[right])
    
16.             log = int(string[left]) - 1
    
17.             while str(log) not in stick :
    
18.                 log -= 1
    
19.             stick.append(string[left])
    
20.             stick.remove(str(log))
    
21.             stick.sort(reverse=True)
    
22. 
    
23.             result = string[:left] + str(log) + "".join(stick)
    
24.             return -1 if len(str(int(result))) != length else int(result)
    
25.     return -1

复制代码

都淡忘

不做了，，，我擦，，，放弃了
刚想到一个反例

fan1993423

Python3005 发表于 2019-11-23 01:09
这样的话能快不少吧

大佬解释一下 string:=str(num)   这个:=是什么意思

Python3005

fan1993423 发表于 2019-11-24 22:57
大佬解释一下 string:=str(num)   这个:=是什么意思

是3.8版本更新的海象运算符，百度一下就行

Lamotu

import random

def app(num):
    strs=str(num)
    ls=list(strs)
    n_strs=""
    lens = len(ls)
    for i in range(lens):
        nstr=random.choice(ls)
        n_strs+=nstr
        ls.remove(nstr)
    new_num=int(n_strs)
    if new_num >= num or len(str(new_num))<len(str(num)):
        print(-1)
    else:
        print(new_num)
        
if __name__ == "__main__":
    while True:
        num=input("请输入数字(按'q'退出)：")
        if num == "q":
            break
        else:
            app(int(num))

阴阳神万物主

题目提案：不用解方程的那个库，解一元一次方程，题目地址：洛谷 P1022
通过的代码：
反正是其他语言的代码.zip (452.34 KB, 下载次数: 1)

2019-11-25 20:10 上传

点击文件名下载附件

里面有可执行文件，但是会调用命令提示符。
没有密码
侧重点不是样式，是结果的数值。

rosemary115

def solve(num):
    str1 = str(num)
    i = len(str1)-1
    if i < 1:
        return -1
    count = i - 1
    while count >= 0:
        if str1[count+1] >= str1[count]:
            count -= 1
        else:
            list1 = list(str1[count:i+1])
            list3 = list1.copy()
            list3.sort()
            x = []
            x.append(list3[list3.index(list1[0])-1])
            list3.remove(x[0])
            for i in range(len(list3)-1,-1,-1):
                x.append(list3[i])
            if count == 0:
                str2 = ''
                if x[0] == '0':
                    return -1
                for each in x:
                    str2 += each
            else:
                str2 = str1[:count]
                for each in x:
                    str2 += each
            return int(str2)
    return -1

yooooly

danteer 发表于 2019-11-22 22:39

dalao能解释下思路吗

zltzlt

阴阳神万物主 发表于 2019-11-25 20:11
题目提案：不用解方程的那个库，解一元一次方程，题目地址：洛谷 P1022
通过的代码：
里面有可执行文件， ...

可以。

danteer

yooooly 发表于 2019-11-25 20:37
dalao能解释下思路吗

从后往前找，遇到一个数(索引count)比后一位大的话，就代表要重写count及之后所有的数。然后提取这些数出来，找到比count这个数小的数中最大的那个和count位置调换，如果恰好count是0(代表在整个数的开头)并且和count位置调换的数是0，返回-1(这情况已经没救了),其他情况下把剩下的数从大到小依次添上去。