Python：每日一题 311
本帖最后由 zltzlt 于 2020-1-21 12:41 编辑今天的题目：
给定一个非负整数，最多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1：
输入：2736
输出：7236
解释：交换数字 2 和数字 7。
示例 2：
输入：9973
输出：9973
解释：不需要交换。
{:10_298:}欢迎大家一起答题！{:10_298:} 本帖最后由 Croper 于 2020-1-21 13:26 编辑
时间复杂度为O(len(n))的写法def func311(n):
sz=str(n) #考虑超大数，转换成字符串处理比取余和除以10要快
maxnum=maxi=0
p=q=-1
for i in range(len(sz)-1,-1,-1):
num=int(sz)
if num<maxnum:
p,q=i,maxi
elif num>maxnum:
maxi,maxnum=i,num
if p!=-1:
sz=sz[:p]+sz+sz+sz+sz
return int(sz) def fun311(num):
temp = list(str(num))
t = temp
p = temp.index(max(temp))
temp = max(temp)
temp = t
return int(''.join(temp)) 本帖最后由 TJBEST 于 2020-1-21 14:06 编辑
def fun301(n):
def split(n):
res = []
while n > 0:
res.append(n%10)
n = n // 10
res.reverse()
return res
def joinStr(arr):
res = arr
for each in arr:
res = res * 10 + each
return res
if n < 10:
return n
arr = split(n)
N = len(arr)
for i in range(0,N - 1):
temp = arr
maxNum = max(arr[(i+1):])
if temp < maxNum:
index = arr.index(maxNum,i + 1)#文档关键字误导人
arr = maxNum
arr = temp
break
return joinStr(arr) Python3005 发表于 2020-1-21 13:12
解答错误
输入：98368
输出：98368
预期结果：98863 TJBEST 发表于 2020-1-21 13:32
解答错误
输入：1993
输出：9193
预期结果：9913 zltzlt 发表于 2020-1-21 14:42
解答错误
输入：1993
版主改了，刚才考虑错了
def fun301(n):
def split(n):
res = []
while n > 0:
res.append(n%10)
n = n // 10
res.reverse()
return res
def joinStr(arr):
res = arr
for each in arr:
res = res * 10 + each
return res
if n < 10:
return n
arr = split(n)
N = len(arr)
for i in range(0,N - 1):
temp = arr
maxNum = max(arr[(i+1):])
if temp < maxNum:
index =N - 1 - arr[(N - 1):i:-1].index(maxNum)#文档关键字误导人
arr = maxNum
arr = temp
break
return joinStr(arr) 本帖最后由 kinkon 于 2020-1-21 16:27 编辑
def f311(n):
tmp = list(str(n))
tmp1 = tmp[:]
res = []
for i in range(len(tmp)-1):
if tmp > tmp:
tmp1, tmp1 = tmp1, tmp1
res.append(''.join(tmp1))
tmp1 = tmp[:]
return res if len(res) >= 1 else n
理解是错的 本帖最后由 wanting-for 于 2020-1-22 01:11 编辑
def maximumSwap(self, A: int) -> int:
A = list(map(int,list(str(A))))
B,result= A.copy(),''
B.sort()
B.reverse()
if B == A:#考虑有序的情况，即从大到小的排列的情况，这种情况交换次数为0
for x in A:
result+=str(x)
return result
else:
num1= 0
for i in range(len(A)-1,-1,-1):
if A[:i] == B[:i]:
break
elif A>num1:
num1 = A
index1 = i
for j in range(0,index1):#从前往后选取最小的
if A < A:
A,A = A,A#找到即退出
break
for x in A:
result+=str(x)
return int(result)
提交后测试了一下，发现了bug，重新修改之后的代码奉上！！！ def fun311(n):
t=''
k={}
str_n=list(str(n))
sort_str_n=sorted(str(n),reverse=True)
rev_str=list(reversed(str_n))
if len(sort_str_n)==len(set(sort_str_n)):
for i in range(len(str_n)):
if str_n!=sort_str_n:
index=str_n.index(sort_str_n)
str_n,str_n=str_n,str_n
break
else:
for i in str_n:
if str_n.count(i)>1:
t+=i
for j in set(t):
k.update({j:len(str_n)-rev_str.index(j)-1})
for i in range(len(str_n)):
if str_n!=sort_str_n:
if sort_str_n not in k:
index=str_n.index(sort_str_n)
str_n,str_n=str_n,str_n
break
else:
index=k]
str_n,str_n=str_n,str_n
break
return int(''.join(str_n))
我的好复杂，等会看Croper大佬的解答 def func311(n1):
n1 = list(str(n1))
n2 = sorted(n1, reverse=True)
for i in range(len(n1)):
if n1 != n2:
maxsur = max(n1)
for j in range(-1, -(len(n1) - i), -1):
if n1 == maxsur:
n1, n1 = n1, n1
break
break
return int(''.join(n1)) 本帖最后由 kinkon 于 2020-1-21 22:57 编辑
版主帮忙测试下，不知道效率怎么样？
def f311(n):
tmp = list(str(n))
t = 0
x=y=m=n=
for i in range(len(tmp)-1):
for j in range(len(tmp)-1,i,-1):
if int(tmp) > int(tmp):
x, y = )] , )]
if x > m:
m, n = x, y
t = 1
if t == 1:
tmp],tmp] = tmp], tmp]
return ''.join(tmp)
else:
return ''.join(tmp)
print(f311(927638)) 本帖最后由 阴阳神万物主 于 2020-1-22 01:18 编辑
终于~~再一次的敲简单的题，泪目。
这个时间复杂度不太会求QAQ
如果不看调用的内置函数(list.index和tuple.index)的时间复杂度的话，应该是 O(1) 最多 81，请问：对不对？
def solve(n):
temp = str(n)
m = int(max(list(temp)))
lst =
while lst and(not lst):lst.pop(0)
rl = lst[::-1]
le = len(temp)
l=r=0
for big in range(m):
if big in lst:
ri = rl.index(big)+1
r = le-ri
nl = lst[:-ri]
# print('调试',nl,big,lst)
for small in range(m-1,big,-1):
if small in nl:
l = temp.index(str(m-small))
if l<r:
break
else:
l = 0
continue
break
else:
r = 0
#print('调试',l,r)
res = temp[:l]+temp+temp+temp+temp if l!=r else temp
return int(res)
if __name__ == '__main__':
print('示例1 输出：',solve(2736))
print('示例2 输出：',solve(9973))
class Solution:
def maximumSwap(self, num: int) -> int:
import functools as f
list1 = list(str(num))
list0 = []
while True:
if len(list1) in (0, 1):
return f.reduce(lambda x, y: 10 * x + y, map(int, list0 + list1))
if list1 == max(list1):
list0.append(list1.pop(0))
else:
break
for i in range(len(list1) - 1, 0, -1):
if list1 == max(list1):
list1, list1 = list1, list1
return f.reduce(lambda x, y: 10 * x + y, map(int, list0 + list1))
刚刚注意到，leetcode对运行时间的测试有波动。
kinkon 发表于 2020-1-21 15:49
理解是错的
解答错误
输入：98368
输出：98638
预期结果：98863 阴阳神万物主 发表于 2020-1-21 23:57
终于~~再一次的敲简单的题，泪目。
这个时间复杂度不太会求QAQ
如果不看调用的内置函数(list.index和tupl ...
解答错误
输入：22341345
输出：22345341
预期结果：52341342 Python3005 发表于 2020-1-21 13:12
不行，9879就不行 zltzlt 发表于 2020-1-22 13:38
解答错误
输入：22341345
那看来我的想法不行，这样吧：
def solve(n):
temp = str(n)
m = int(max(list(temp)))
lst =
while lst and(not lst):lst.pop(0)
rl = lst[::-1]
le = len(temp)
l=r=0
for big in range(m):
if big in lst:
ri = rl.index(big)+1
r = le-ri
nl = lst[:-ri]
# print('调试',nl,big,lst)
for small in range(len(nl)):
if nl > big:
l = small
if l<r:
break
else:
continue
break
else:
r = 0
#print('调试',l,r)
res = temp[:l]+temp+temp+temp+temp if l!=r else temp
return int(res)
if __name__ == '__main__':
print('示例1 输出：',solve(2736))
print('示例2 输出：',solve(9973))
哇，受宠若惊，我那么复杂的代码是最佳答案，谢谢版主{:10_245:} fan1993423 发表于 2020-1-22 17:39
哇，受宠若惊，我那么复杂的代码是最佳答案，谢谢版主
鼓励鼓励你{:10_256:}
页:
[1]
2