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

zltzlt

今天的题目：

给定一个整数 n，返回比它小的数。这个数有如下要求：
1. n 的位数可以交换，但是不能修改。例如 21，你可以将 1 和 2 交换，得到 12，但不能用 2 - 1 得到 11
2. 当你找不到一个比 n 小的整数时，返回 -1
3. 当 0 不得不占首位时，返回 -1（首位不能为 0）

示例 1：

输入：21
输出：12

示例 2：

输入：531
输出：513

示例 3：

输入：135
输出：-1

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

danteer

2019-11-22 22:39:27

1. def solve(num):
   
2.     str1 = str(num)
   
3.     i = len(str1)-1
   
4.     if i < 1:
   
5.         return -1
   
6.     count = i - 1
   
7.     while count >= 0:
   
8.         if str1[count+1] >= str1[count]:
   
9.             count -= 1
   
10.         else:
    
11.             list1 = list(str1[count:i+1])
    
12.             list3 = list1.copy()
    
13.             list3.sort()
    
14.             x = []
    
15.             x.append(list3[list3.index(list1[0])-1])
    
16.             list3.remove(x[0])
    
17.             for i in range(len(list3)-1,-1,-1):
    
18.                 x.append(list3[i])
    
19.             if count == 0:
    
20.                 str2 = ''
    
21.                 if x[0] == '0':
    
22.                     return -1
    
23.                 for each in x:
    
24.                     str2 += each
    
25.             else:
    
26.                 str2 = str1[:count]
    
27.                 for each in x:
    
28.                     str2 += each
    
29.             return int(str2)
    
30.     return -1

复制代码

跳转到最佳答案楼层

danteer

1. def solve(num):
   
2.     str1 = str(num)
   
3.     i = len(str1)-1
   
4.     if i < 1:
   
5.         return -1
   
6.     count = i - 1
   
7.     while count >= 0:
   
8.         if str1[count+1] >= str1[count]:
   
9.             count -= 1
   
10.         else:
    
11.             list1 = list(str1[count:i+1])
    
12.             list3 = list1.copy()
    
13.             list3.sort()
    
14.             x = []
    
15.             x.append(list3[list3.index(list1[0])-1])
    
16.             list3.remove(x[0])
    
17.             for i in range(len(list3)-1,-1,-1):
    
18.                 x.append(list3[i])
    
19.             if count == 0:
    
20.                 str2 = ''
    
21.                 if x[0] == '0':
    
22.                     return -1
    
23.                 for each in x:
    
24.                     str2 += each
    
25.             else:
    
26.                 str2 = str1[:count]
    
27.                 for each in x:
    
28.                     str2 += each
    
29.             return int(str2)
    
30.     return -1

复制代码

Unicorn#

最后一位也不能为0吗

Python3005

1. import itertools
   
2. def fun(num):
   
3.         for each in itertools.permutations((string := str(num)),len(string)):
   
4.                 if (temp := int(''.join(each))) < num and len(str(temp)) == len(string):
   
5.                         return temp
   
6.         else:
   
7.                 return -1

复制代码

加一句过滤一下应该能快不少：

1. def fun(num):
   
2.         if sorted(list(str(num))) == list(str(num)):
   
3.                 return -1
   
4.         else:
   
5.                 for each in itertools.permutations((string := str(num)),len(string)):
   
6.                         if (temp := int(''.join(each))) < num and len(str(temp)) == len(string):
   
7.                                 return temp
   
8.                 else:
   
9.                         return -1

复制代码

阴阳神万物主

示例2 是返回 135 或者 351 或者 315 或者 513 都行吗？还是挑交换次数小的输出？交换是只能相邻的进行交换还是跳着也能交换？

peicd

姑且认为是首位不是首尾，打错了，不然整句话有矛盾

1. import itertools
   
2. def abc(a):
   
3.     for each in itertools.permutations(str(a),len(str(a))):
   
4.         b=''.join(each)
   
5.         if int(b)<a and  each[0]!='0':
   
6.             return b
   
7.     return -1

复制代码

凌九霄

1. def next_smaller(n: int):
   
2.     s, t, z = list(str(n)), [], ''
   
3.     try:
   
4.         while 1:
   
5.             t.append(s.pop())
   
6.             if int(t[-1]) < int(s[-1]):
   
7.                 z = s.pop()
   
8.                 t.append(z)
   
9.                 break
   
10.         t = sorted(t)
    
11.         z = [t.pop(t.index(z) - 1)]
    
12.         r = int(''.join(s + z + t[::-1]))
    
13.         if len(str(r)) == len(str(n)):
    
14.             return r
    
15.         else:
    
16.             return -1
    
17.     except IndexError:
    
18.         return -1

复制代码

凌九霄

peicd 发表于 2019-11-22 23:39
姑且认为是首位不是首尾，打错了，不然整句话有矛盾

排列组合当然是没有问题，但是，如果这个数字稍大一点，呵呵...

凌九霄

Python3005 发表于 2019-11-22 23:37

跑个20位数试试

凌九霄

阴阳神万物主 发表于 2019-11-22 23:37
示例2 是返回 135 或者 351 或者 315 或者 513 都行吗？还是挑交换次数小的输出？交换是只能相邻的进行交换 ...

我认为是返回比原数小的最大的那个数

Stubborn

阴阳神万物主 发表于 2019-11-22 23:37
示例2 是返回 135 或者 351 或者 315 或者 513 都行吗？还是挑交换次数小的输出？交换是只能相邻的进行交换 ...

对数字进行位交换，找一个比他小的数返回

peicd

亲测，如果位数比较多，例如几百上万位，set后有微弱优势，如果位数比较少，例如123，不set有微弱优势

1. def abc(num):
   
2.     b=''
   
3.     num = str(num)
   
4.     num1=num
   
5.     for i in range(len(num)):
   
6.         Num = set(num)
   
7.         a = min(Num)
   
8.         if a=='0' and i==0:
   
9.             Num.discard('0')
   
10.             a=min(Num)
    
11.         b+=a
    
12.         num=num.replace(a,'',1)
    
13.         if a<num1[i]:
    
14.             return b+num
    
15.     return -1

复制代码

Python3005

凌九霄 发表于 2019-11-23 00:09
跑个20位数试试

这样的话能快不少吧

1. def fun(num):
   
2.         if sorted(list(str(num))) == list(str(num)):
   
3.                 return -1
   
4.         else:
   
5.                 for each in itertools.permutations((string := str(num)),len(string)):
   
6.                         if (temp := int(''.join(each))) < num and len(str(temp)) == len(string):
   
7.                                 return temp
   
8.                 else:
   
9.                         return -1

复制代码

zltzlt

Unicorn# 发表于 2019-11-22 22:56
最后一位也不能为0吗

可以。

zltzlt

阴阳神万物主 发表于 2019-11-22 23:37
示例2 是返回 135 或者 351 或者 315 或者 513 都行吗？还是挑交换次数小的输出？交换是只能相邻的进行交换 ...

返回 135、351、315、513 等等最小但离原数最大的那一个

zltzlt

peicd 发表于 2019-11-23 00:59

解答错误

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

danteer

1. def func(num):
   
2.     str1 = str(num)
   
3.     if len(str1) < 2:
   
4.         return -1
   
5.     for i in range(0,len(str1)-1):
   
6.         if str1[i] > str1[i+1]:
   
7.             if i == 0 and str1[i+1] == '0':
   
8.                 continue
   
9.             if i+1 != len(str1) - 1:
   
10.                 str2 = str1[:i] + str1[i+1] + str1[i] + str1[i+2:]
    
11.             else:
    
12.                 str2 = str1[:i] + str1[i+1] + str1[i]
    
13.             return int(str2)
    
14.     return -1

复制代码

以上是返回一个随机的更小的数
以下是返回一个最大的更小的数

1. import itertools
   
2. 
   
3. def solve(num):
   
4.     str1 = str(num)
   
5.     i = len(str1)-1
   
6.     if i < 1:
   
7.         return -1
   
8.     count = i - 1
   
9.     while count >= 0:
   
10.         if str1[count+1] >= str1[count]:
    
11.             count -= 1
    
12.         else:
    
13.             list1 = list(str1[count:i+1])
    
14.             list3 = list1.copy()
    
15.             list3.sort()
    
16.             list2 = list(itertools.permutations(list3,len(list1)))
    
17.             x = list2[list2.index(tuple(list1)) - 1]
    
18.             if count == 0:
    
19.                 str2 = ''
    
20.                 if x[0] == '0':
    
21.                     return -1
    
22.                 for each in x:
    
23.                     str2 += each
    
24.             else:
    
25.                 str2 = str1[:count]
    
26.                 for each in x:
    
27.                     str2 += each
    
28.             return int(str2)
    
29.     return -1

复制代码

peicd

zltzlt 发表于 2019-11-23 08:37
解答错误

输入：135

重新改了一下。麻烦再试一下

__mrsq__

1. def fun279(num):
   
2.     s = str(num)
   
3.     n = len(s)
   
4.     res = ''
   
5.     if n==1:
   
6.         return -1
   
7.     for i in range(n-1,0,-1):
   
8.         if s[i] < s[i-1]:
   
9.             res = s[0:i-1]+s[i]+s[i-1]+s[i+1:]
   
10.             if res[0]!= '0':
    
11.                 return int(res)
    
12.             
    
13.     for i in res[2:]:
    
14.         if i != '0':
    
15.             if i >= res[1]:
    
16.                 return -1
    
17.             else:
    
18.                 return int(i+s[1:s.index(i)]+s[0]+s[s.index(i)+1:])
    
19. 
    
20.     return -1

复制代码

都淡忘

我仔细看了半小时评论加例子才看清题意，佛了，意思说的不明不白的
题意是这样的？
第一，交换是任意交换，并且可以是多次交换
第二，最后输出的数字是所有比原数小的数字中的最大值
找不到这样相同位数的数字就-1
？