Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.
Example 1:
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973
Output: 9973
Explanation: No swap.
Note:
- The given number is in the range [0, 10^8 ]
Solutions
刚开始一脸懵逼,因为不想用暴力求解,结果想半天越想懵,还是参考后用暴力解了……
class Solution(object):
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
str_num = list(str(num))
n = len(str_num)
res = str_num[:]
for i in range(n):
for j in range(i+1, n):
str_num[i], str_num[j] = str_num[j], str_num[i]
if res < str_num:
res = str_num[:]
str_num[i], str_num[j] = str_num[j], str_num[i]
return ''.join(res)
# Runtime: 20 ms, faster than 67.02% of Python online submissions for Maximum Swap.
# Memory Usage: 11.8 MB, less than 36.89% of Python online submissions for Maximum Swap.
按照规律的思路:
- 从前往后找到第一升序的位置:R[i-1] < R[i];
- 再从前往后找到比后半部分 R[i:] 的最大值小的位置,交换这两个数即可。
class Solution(object):
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
i, R = 1, list(str(num))
n = len(R)
while i < n and R[i-1] >= R[i]:
# 找到第一个升序的 i
i += 1
if i < n:
j, k = 0, str(num).rfind(max(R[i:]))
while j < i and R[j] >= R[k]:
j += 1
R[j], R[k] = R[k], R[j]
return ''.join(R)
# Runtime: 8 ms, faster than 99.13% of Python online submissions for Maximum Swap.
# Memory Usage: 11.9 MB, less than 22.13% of Python online submissions for Maximum Swap.