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

zltzlt

__mrsq__ 发表于 2019-11-23 17:43
修改了一下，不知道对不对，求测试@zltzlt

解答错误

输入：1234567908
输出：1234567098
预期结果：1234567890

华一仙

1. """
   
2. 不妨设 num = 5431234
   
3.                ^
   
4.                j(3) 临界点（后面是升序）；记 j 对应的数字为 n
   
5. 
   
6. step 1: 从后向前，找到临界点 j
   
7. step 2: 从后向前，找到第一个小于 n 的数，并且两数交换 => num' = 5421334
   
8. step 3: j 后面的数做 reverse                       => num" = 5424331
   
9. 
   
10. 最后再关注一下首位为 0 的情况
    
11. """
    
12. 
    
13. 
    
14. def f279(num):
    
15.     if num < 10:
    
16.         return -1
    
17. 
    
18.     lst = list(str(num))
    
19.     n = len(lst)
    
20.     i = n - 1
    
21.     while i > 0 and lst[i-1] <= lst[i]:  # 漏了个等于号
    
22.         i -= 1
    
23.     if i == 0:
    
24.         return -1
    
25. 
    
26.     j = i - 1
    
27.     i = n - 1
    
28.     while lst[j] <= lst[i]:
    
29.         i -= 1
    
30.     lst[i], lst[j] = lst[j], lst[i]
    
31.     tmp = lst[j+1:]
    
32.     tmp.reverse()
    
33.     res = ''.join(lst[:j+1] + tmp)
    
34.     return -1 if res[0] == '0' else int(res)

复制代码

zltzlt

华一仙 发表于 2019-11-23 17:53
这回不在原来的楼层改了

出错：IndexError: list index out of range

zltzlt

一个账号 发表于 2019-11-23 17:09
@zltzlt 这样应该可以了吧：

解答错误

输入：907
输出：'709'
预期结果：790

一个账号

zltzlt 发表于 2019-11-23 17:44
解答错误

输入：1234567908

错了，预期结果应该是：1023456789

zltzlt

一个账号 发表于 2019-11-23 17:56
错了，预期结果应该是：1023456789

不是，返回所有比原数小的数中最大的那个数

一个账号

zltzlt 发表于 2019-11-23 17:56
解答错误

输入：907

不是 709 吗？

zltzlt

一个账号 发表于 2019-11-23 17:57
不是 709 吗？

不是，返回所有比原数小的数中最大的那个数

爱尔兰咖啡

1. #未考虑负数的情况，思路一样
   
2. def f(x):
   
3.     x=str(x)
   
4.     a=list(x)
   
5.     b=a[:]
   
6.     for i in range(len(a)-1):
   
7.            a1=max(a[:i+1])
   
8.            n=a.index(a1)
   
9.            if a1>a[i+1] and a[i+1]!='0':
   
10.                a[n],a[i+1]=a[i+1],a[n]
    
11.                break
    
12.     if a==b:
    
13.         return -1
    
14.     else:
    
15.         return ''.join(a)
    
16. print(f(21))
    
17. print(f(531))
    
18. print(f(135))

复制代码

zltzlt

爱尔兰咖啡 发表于 2019-11-23 18:00

解答错误

输入：907
输出：'709'
预期结果：790

一个账号

zltzlt 发表于 2019-11-23 17:58
不是，返回所有比原数小的数中最大的那个数

额......好吧，我再改。

danteer

我呢我呢

zltzlt

danteer 发表于 2019-11-23 18:13
我呢我呢

超时，总执行时长超过 12 秒

__mrsq__

1. def fun(num):
   
2.     s = str(num)
   
3.     m = 0
   
4.     while s[-1]=='0':
   
5.         m=m+1
   
6.         s=s[:-1]
   
7.     n = len(s)
   
8.     if '0' in s:
   
9.         l = s[::-1]
   
10.         a = n - l.index('0')-1
    
11.     if n==1:
    
12.         return -1
    
13.    
    
14.     for i in range(n-1,0,-1):
    
15.         
    
16.         if s[i] < s[i-1]:
    
17.             if s[i]=='0' and s[a+1] < s[i-1]:
    
18.                 tem =''
    
19.                 Flag =0
    
20.                 for j in s[a+1:][::-1]:
    
21.                     if Flag == 0:
    
22.                         if s[i-1] <= j:
    
23.                             tem = tem + j
    
24.                         else:
    
25.                             Flag =1
    
26.                             tem = j + s[i-1] + tem
    
27.                     else:
    
28.                         tem = tem +j
    
29.             
    
30.                 res = s[0:i-1] + tem +(a-i+1+m)*'0'
    
31.             else:
    
32.                 tem =''
    
33.                 Flag =0
    
34.                 for j in s[i:][::-1]:
    
35.                     if Flag == 0:
    
36.                         if s[i-1] <= j:
    
37.                             tem = tem + j
    
38.                         else:
    
39.                             Flag =1
    
40.                             tem = j + s[i-1] + tem
    
41.                     else:
    
42.                         tem = tem +j
    
43.                 res = s[0:i-1] + tem +(m)*'0'
    
44.             return int(res) if res[0]!='0' else -1
    
45.             
    
46.     return -1
    
47.         

复制代码

zxcbcv

脑瓜仁疼

zltzlt

danteer 发表于 2019-11-23 19:35

恭喜通过！

执行用时：816 ms

zltzlt

__mrsq__ 发表于 2019-11-23 19:55

解答错误

输入：315
输出：135
预期结果：153

都淡忘

我改变了一下思路，从末位开始考虑，用字典哈希会不会快一点

1. def f279(num):
   
2. 
   
3.     st = str(num)
   
4.     le = len(st)
   
5.     d = {i: st[i] for i in range(len(st))}
   
6. 
   
7.     def 交换(f, l: dict):
   
8.         flag = f - 1
   
9.         for i in range(flag - 1, -1, -1):
   
10.             if l[i] > l[f - 1]:
    
11.                 l[i], l[f - 1] = l[f - 1], l[i]
    
12.                 if l[0] != "0":
    
13.                     return (i + 1, l)
    
14.         else:
    
15.             if flag == -1:  # 调用递归之前看看有无必要
    
16.                 return -1
    
17.             return 交换(flag, l)
    
18. 
    
19.     r = 交换(le, d)
    
20.     if r == -1:  # -1就是不符合情况
    
21.         return -1
    
22.     temp1_count = 0
    
23.     temp1 = []
    
24.     while temp1_count < r[0]:
    
25.         temp1.append(r[1][temp1_count])
    
26.         temp1_count += 1
    
27.     temp2_count = r[0]
    
28.     temp2 = []
    
29.     while temp2_count <= le - 1:
    
30.         temp2.append(r[1][temp2_count])
    
31.         temp2_count += 1
    
32.     temp2.sort(reverse=True)
    
33.     temp1.extend(temp2)
    
34.     return int(''.join(temp1))

复制代码

__mrsq__

1. def fun(num):
   
2.     s = str(num)
   
3.     m = 0
   
4.     while s[-1]=='0':
   
5.         m=m+1
   
6.         s=s[:-1]
   
7.     n = len(s)
   
8.     if '0' in s:
   
9.         l = s[::-1]
   
10.         a = n - l.index('0')-1
    
11.     if n==1:
    
12.         return -1
    
13.    
    
14.     for i in range(n-1,0,-1):
    
15.         
    
16.         if s[i] < s[i-1]:
    
17.             if s[i]=='0' and s[a+1] < s[i-1]:
    
18.                 tem =''
    
19.                 Flag =0
    
20.                 for j in s[a+1:][::-1]:
    
21.                     if Flag == 0:
    
22.                         if s[i-1] <= j:
    
23.                             tem = tem + j
    
24.                         else:
    
25.                             Flag =1
    
26.                             tem = j + tem + s[i-1]
    
27.                     else:
    
28.                         tem = tem +j
    
29.             
    
30.                 res = s[0:i-1] + tem +(a-i+1+m)*'0'
    
31.             else:
    
32.                 tem =''
    
33.                 Flag =0
    
34.                 for j in s[i:][::-1]:
    
35.                     if Flag == 0:
    
36.                         if s[i-1] <= j:
    
37.                             tem = tem + j
    
38.                         else:
    
39.                             Flag =1
    
40.                             tem = j + tem + s[i-1]
    
41.                     else:
    
42.                         tem = tem +j
    
43.                 res = s[0:i-1] + tem +(m)*'0'
    
44.             return int(res) if res[0]!='0' else -1
    
45.             
    
46.     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=len(list_n)-1
   
9.         max_n=max(list_n)
   
10.         copy=list_n[:]
    
11.         while i<j and j>0:
    
12.             if i == -1:
    
13.                 j-=1
    
14.                 i=j-1
    
15.                 continue
    
16.             if list_n[j] ==max_n:
    
17.                 j-=1
    
18.                 i=j-1
    
19.                 continue
    
20.             if list_n[i]>list_n[j]:
    
21.                 list_n[i],list_n[j] = list_n[j],list_n[i]
    
22.                 exchange=list_n[i+1:]
    
23.                 exchange.sort(reverse=True)
    
24.                 list_n[i + 1:]=exchange
    
25.                 break
    
26.             else:
    
27.                 i-=1
    
28. 
    
29.         if copy!=list_n and list_n[0]!=0:
    
30.             result=''.join(list(map(lambda x: str(x), list_n)))
    
31.     return result
    
32. 
    
33. 
    
34. 
    
35. 
    
36. 
    

复制代码