0%

LeetCode 670 最大交换 (暴力+贪心、Python)

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-swap

问题描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1 :

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

示例 2 :

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

注意:

给定数字的范围是 [0, 108]

方法一:暴力法

两重循环,每次交换两个相邻的数,取最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
T = int(input())

for i in range (T):
res = ""
a = input()
res = int(a)
for i in range (len(a)):
for j in range (i+1, len(a)):
b = list(a)
b[i], b[j] = b[j], b[i]
m = int(''.join(b))
res = max(res, m)
print(res)

方法二:贪心算法

  • 我们将计算 last[d] = i,最后一次出现的数字 d(如果存在)的索引i。
  • 然后,从左到右扫描数字时,如果将来有较大的数字,我们将用最大的数字交换;如果有多个这样的数字,我们将用最开始遇到的数字交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
T = int(input())

def fu(a):
t = list(a)
pos = [0 for _ in range (10)]
# 记录每个数字出现的最后一次出现的下标
for i in range (len(a)):
pos[int(a[i])] = i
# 从左向右扫描,找到当前位置右边的最大的数字并交换
for i in range (len(a)-1):
# 找最大,所以倒着找
for j in range (9, int(t[i]), -1):
if pos[j] > i:
t[pos[j]], t[i] = t[i], t[pos[j]]
# 只允许交换一次,因此直接返回
return int(''.join(t))
return a

for v in range (T):
a = input()
res = fu(a)
print(res)
-------------    本文结束  感谢您的阅读    -------------