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

zltzlt

今天的题目：

给定一个非负整数，最多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1：

输入：2736
输出：7236
解释：交换数字 2 和数字 7。

示例 2：

输入：9973
输出：9973
解释：不需要交换。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

fan1993423

2020-1-21 16:57:10

1. def fun311(n):
   
2.     t=''
   
3.     k={}
   
4.     str_n=list(str(n))
   
5.     sort_str_n=sorted(str(n),reverse=True)
   
6.     rev_str=list(reversed(str_n))
   
7.     if len(sort_str_n)==len(set(sort_str_n)):
   
8.         for i in range(len(str_n)):
   
9.             if str_n[i]!=sort_str_n[i]:
   
10.                 index=str_n.index(sort_str_n[i])
    
11.                 str_n[i],str_n[index]=str_n[index],str_n[i]
    
12.                 break
    
13.     else:
    
14.         for i in str_n:
    
15.             if str_n.count(i)>1:
    
16.                 t+=i
    
17.         for j in set(t):
    
18.             k.update({j:len(str_n)-rev_str.index(j)-1})
    
19.         for i in range(len(str_n)):
    
20.             if str_n[i]!=sort_str_n[i]:
    
21.                 if sort_str_n[i] not in k:
    
22.                     index=str_n.index(sort_str_n[i])
    
23.                     str_n[i],str_n[index]=str_n[index],str_n[i]
    
24.                     break
    
25.                 else:
    
26.                     index=k[sort_str_n[i]]
    
27.                     str_n[i],str_n[index]=str_n[index],str_n[i]
    
28.                     break
    
29.     return int(''.join(str_n))

复制代码

我的好复杂，等会看Croper大佬的解答

跳转到最佳答案楼层

Croper

时间复杂度为O(len(n))的写法

1. def func311(n):
   
2.     sz=str(n) #考虑超大数，转换成字符串处理比取余和除以10要快
   
3.     maxnum=maxi=0
   
4.     p=q=-1
   
5.     for i in range(len(sz)-1,-1,-1):
   
6.         num=int(sz[i])
   
7.         if num<maxnum:
   
8.             p,q=i,maxi
   
9.         elif num>maxnum:
   
10.             maxi,maxnum=i,num
    
11.     if p!=-1:
    
12.         sz=sz[:p]+sz[q]+sz[p+1:q]+sz[p]+sz[q+1:]
    
13.     return int(sz)

复制代码

Python3005

1. def fun311(num):
   
2.         temp = list(str(num))
   
3.         t = temp[0]
   
4.         p = temp.index(max(temp))
   
5.         temp[0] = max(temp)
   
6.         temp[p] = t
   
7.         return int(''.join(temp))

复制代码

TJBEST

1. def fun301(n):
   
2.     def split(n):
   
3.         res = []
   
4.         while n > 0:
   
5.             res.append(n%10)
   
6.             n = n // 10
   
7.         res.reverse()
   
8.         return res
   
9.     def joinStr(arr):
   
10.         res = arr[0]
    
11.         for each in arr[1:]:
    
12.             res = res * 10 + each
    
13.         return res
    
14.     if n < 10:
    
15.         return n
    
16.     arr = split(n)
    
17.     N = len(arr)
    
18.     for i in range(0,N - 1):
    
19.         temp = arr[i]
    
20.         maxNum = max(arr[(i+1):])
    
21.         if temp < maxNum:
    
22.             index = arr.index(maxNum,i + 1)#文档关键字误导人
    
23.             arr[i] = maxNum
    
24.             arr[index] = temp
    
25.             break
    
26.     return joinStr(arr)

复制代码

zltzlt

Python3005 发表于 2020-1-21 13:12

解答错误

输入：98368
输出：98368
预期结果：98863

zltzlt

TJBEST 发表于 2020-1-21 13:32

解答错误

输入：1993
输出：9193
预期结果：9913

TJBEST

zltzlt 发表于 2020-1-21 14:42
解答错误

输入：1993

版主改了，刚才考虑错了

1. def fun301(n):
   
2.     def split(n):
   
3.         res = []
   
4.         while n > 0:
   
5.             res.append(n%10)
   
6.             n = n // 10
   
7.         res.reverse()
   
8.         return res
   
9.     def joinStr(arr):
   
10.         res = arr[0]
    
11.         for each in arr[1:]:
    
12.             res = res * 10 + each
    
13.         return res
    
14.     if n < 10:
    
15.         return n
    
16.     arr = split(n)
    
17.     N = len(arr)
    
18.     for i in range(0,N - 1):
    
19.         temp = arr[i]
    
20.         maxNum = max(arr[(i+1):])
    
21.         if temp < maxNum:
    
22.             index =N - 1 - arr[(N - 1):i:-1].index(maxNum)#文档关键字误导人
    
23.             arr[i] = maxNum
    
24.             arr[index] = temp
    
25.             break
    
26.     return joinStr(arr)

复制代码

kinkon

1. def f311(n):
   
2.     tmp = list(str(n))   
   
3.     tmp1 = tmp[:]
   
4.     res = []
   
5.     for i in range(len(tmp)-1):
   
6.         if tmp[i+1] > tmp[i]:
   
7.             tmp1[i], tmp1[i+1] = tmp1[i+1], tmp1[i]            
   
8.             res.append(''.join(tmp1))
   
9.             tmp1 = tmp[:]        
   
10.     return res[0] if len(res) >= 1 else n

复制代码

理解是错的

wanting-for

1. def maximumSwap(self, A: int) -> int:
   
2.     A = list(map(int,list(str(A))))
   
3.     B,result= A.copy(),''
   
4.     B.sort()
   
5.     B.reverse()
   
6.     if B == A:#考虑有序的情况，即从大到小的排列的情况，这种情况交换次数为0
   
7.         for x in A:
   
8.             result+=str(x)
   
9.         return result
   
10.     else:
    
11.         num1= 0
    
12.         for i in range(len(A)-1,-1,-1):
    
13.             if A[:i] == B[:i]:
    
14.                 break
    
15.             elif A[i]>num1:
    
16.                 num1 = A[i]
    
17.                 index1 = i
    
18.         for j in range(0,index1):#从前往后选取最小的
    
19.             if A[j] < A[index1]:
    
20.                 A[j],A[index1] = A[index1],A[j]#找到即退出
    
21.                 break
    
22.         for x in A:
    
23.             result+=str(x)
    
24.     return int(result)

复制代码

提交后测试了一下，发现了bug，重新修改之后的代码奉上！！！

fan1993423

1. def fun311(n):
   
2.     t=''
   
3.     k={}
   
4.     str_n=list(str(n))
   
5.     sort_str_n=sorted(str(n),reverse=True)
   
6.     rev_str=list(reversed(str_n))
   
7.     if len(sort_str_n)==len(set(sort_str_n)):
   
8.         for i in range(len(str_n)):
   
9.             if str_n[i]!=sort_str_n[i]:
   
10.                 index=str_n.index(sort_str_n[i])
    
11.                 str_n[i],str_n[index]=str_n[index],str_n[i]
    
12.                 break
    
13.     else:
    
14.         for i in str_n:
    
15.             if str_n.count(i)>1:
    
16.                 t+=i
    
17.         for j in set(t):
    
18.             k.update({j:len(str_n)-rev_str.index(j)-1})
    
19.         for i in range(len(str_n)):
    
20.             if str_n[i]!=sort_str_n[i]:
    
21.                 if sort_str_n[i] not in k:
    
22.                     index=str_n.index(sort_str_n[i])
    
23.                     str_n[i],str_n[index]=str_n[index],str_n[i]
    
24.                     break
    
25.                 else:
    
26.                     index=k[sort_str_n[i]]
    
27.                     str_n[i],str_n[index]=str_n[index],str_n[i]
    
28.                     break
    
29.     return int(''.join(str_n))

复制代码

我的好复杂，等会看Croper大佬的解答

hrp

1. def func311(n1):
   
2.     n1 = list(str(n1))
   
3.     n2 = sorted(n1, reverse=True)
   
4.     for i in range(len(n1)):
   
5.         if n1[i] != n2[i]:
   
6.             maxsur = max(n1[i + 1:])
   
7.             for j in range(-1, -(len(n1) - i), -1):
   
8.                 if n1[j] == maxsur:
   
9.                     n1[i], n1[j] = n1[j], n1[i]
   
10.                     break
    
11.             break
    
12.     return int(''.join(n1))

复制代码

kinkon

版主帮忙测试下，不知道效率怎么样？

1. def f311(n):
   
2.     tmp = list(str(n))
   
3.     t = 0
   
4.    
   
5.     x=y=m=n=[0,0]
   
6.     for i in range(len(tmp)-1):
   
7.         for j in range(len(tmp)-1,i,-1):
   
8.             if int(tmp[j]) > int(tmp[i]):
   
9.                 x, y = [j, int(tmp[j])] , [i, int(tmp[i])]
   
10.                
    
11.                 if x[1] > m[1]:
    
12.                     m, n = x, y
    
13.                     t = 1
    
14.    
    
15.     if t == 1:
    
16.         tmp[m[0]],tmp[n[0]] = tmp[n[0]], tmp[m[0]]
    
17.         return ''.join(tmp)
    
18.     else:
    
19.         return ''.join(tmp)
    
20.         
    
21. print(f311(927638))

复制代码

阴阳神万物主

终于~~再一次的敲简单的题，泪目。
这个时间复杂度不太会求QAQ
如果不看调用的内置函数(list.index和tuple.index)的时间复杂度的话，应该是 O(1) 最多 81，请问：对不对？

1. def solve(n):
   
2.     temp = str(n)
   
3.     m = int(max(list(temp)))
   
4.     lst = [m-int(x) for x in temp]
   
5.     while lst and(not lst[0]):lst.pop(0)
   
6.     rl = lst[::-1]
   
7.     le = len(temp)
   
8.     l=r=0
   
9.     for big in range(m):
   
10.         if big in lst:
    
11.             ri = rl.index(big)+1
    
12.             r = le-ri
    
13.             nl = lst[:-ri]
    
14.     #        print('调试',nl,big,lst)
    
15.             for small in range(m-1,big,-1):
    
16.                 if small in nl:
    
17.                     l = temp.index(str(m-small))
    
18.                     if l<r:
    
19.                         break
    
20.             else:
    
21.                 l = 0
    
22.                 continue
    
23.             break
    
24.     else:
    
25.         r = 0
    
26.     #print('调试',l,r)
    
27.     res = temp[:l]+temp[r]+temp[l+1:r]+temp[l]+temp[r+1:] if l!=r else temp
    
28.     return int(res)
    
29. if __name__ == '__main__':
    
30.     print('示例1 输出：',solve(2736))
    
31.     print('示例2 输出：',solve(9973))
    

复制代码

冬雪雪冬

1. class Solution:
   
2.     def maximumSwap(self, num: int) -> int:
   
3.         import functools as f
   
4.         list1 = list(str(num))
   
5.         list0 = []
   
6.         while True:
   
7.             if len(list1) in (0, 1):
   
8.                 return f.reduce(lambda x, y: 10 * x + y, map(int, list0 + list1))
   
9.             if list1[0] == max(list1):
   
10.                 list0.append(list1.pop(0))
    
11.             else:
    
12.                 break
    
13.         for i in range(len(list1) - 1, 0, -1):
    
14.             if list1[i] == max(list1):
    
15.                 list1[i], list1[0] = list1[0], list1[i]
    
16.                 return f.reduce(lambda x, y: 10 * x + y, map(int, list0 + list1))

复制代码

刚刚注意到，leetcode对运行时间的测试有波动。

zltzlt

kinkon 发表于 2020-1-21 15:49
理解是错的

解答错误

输入：98368
输出：98638
预期结果：98863

zltzlt

阴阳神万物主 发表于 2020-1-21 23:57
终于~~再一次的敲简单的题，泪目。
这个时间复杂度不太会求QAQ
如果不看调用的内置函数(list.index和tupl ...

解答错误

输入：22341345
输出：22345341
预期结果：52341342

小甲鱼de粉丝

Python3005 发表于 2020-1-21 13:12

不行，9879就不行

阴阳神万物主

zltzlt 发表于 2020-1-22 13:38
解答错误

输入：22341345

那看来我的想法不行，这样吧：

1. def solve(n):
   
2.     temp = str(n)
   
3.     m = int(max(list(temp)))
   
4.     lst = [m-int(x) for x in temp]
   
5.     while lst and(not lst[0]):lst.pop(0)
   
6.     rl = lst[::-1]
   
7.     le = len(temp)
   
8.     l=r=0
   
9.     for big in range(m):
   
10.         if big in lst:
    
11.             ri = rl.index(big)+1
    
12.             r = le-ri
    
13.             nl = lst[:-ri]
    
14.     #        print('调试',nl,big,lst)
    
15.             for small in range(len(nl)):
    
16.                 if nl[small] > big:
    
17.                     l = small
    
18.                     if l<r:
    
19.                         break
    
20.             else:
    
21.                 continue
    
22.             break
    
23.     else:
    
24.         r = 0
    
25.     #print('调试',l,r)
    
26.     res = temp[:l]+temp[r]+temp[l+1:r]+temp[l]+temp[r+1:] if l!=r else temp
    
27.     return int(res)
    
28. if __name__ == '__main__':
    
29.     print('示例1 输出：',solve(2736))
    
30.     print('示例2 输出：',solve(9973))
    

复制代码

fan1993423

哇，受宠若惊，我那么复杂的代码是最佳答案，谢谢版主

zltzlt

fan1993423 发表于 2020-1-22 17:39
哇，受宠若惊，我那么复杂的代码是最佳答案，谢谢版主

鼓励鼓励你