题目描述

leetcode670.最大交换

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

示例 1 :

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

示例 2 :

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

注意:

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

题解——脑筋急转弯——模拟选择排序

思路

考虑最优解:容易看出,尽量使最前面的数最大,是最好的结果。也就是说,如果后面的最大值比第一个数大,就将它和第一个数交换并返回答案;否则考虑第二个数……如果到最后发现已经是倒序排列了,就不做交换,直接返回。

其实,这不就是选择排序的过程嘛!依次找到最大的数、次大的数……并与第一个数、第二个数……交换。不同的是,我们最多只能执行一次交换。所以,我们套用选择排序的模板,如果执行了交换就直接返回。

值得注意的是,内层循环应当从后往前进行,这是因为在有两个最大值时,使用后面的更好

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int maximumSwap(int num) {
string s=to_string(num);//转成字符串
for(int i=0;i<s.size();++i)//选择排序模板
{
int pos=i;
for(int j=s.size()-1;j>i;--j)//内层循环从后往前
if(s[pos]<s[j])
pos=j;
if(pos!=i)//如果最大的不是i,交换并返回
{
swap(s[i],s[pos]);
return stoi(s);
}
}
return num;//倒序排列,直接返回
}
};