[LeetCode] 670. Maximum Swap 最大置换
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, 108]
这道题给了一个数字，我们有一次机会可以置换该数字中的任意两位，让返回置换后的最大值，当然如果当前数字就是最大值，也可以选择不置换，直接返回原数。那么最简单粗暴的方法当然就是将所有可能的置换都进行一遍，然后更新结果 res，取其中较大的数字，这样一定会得到置换后的最大数字，这里使用了整型数和字符串之间的相互转换，参见代码如下：
解法一：
class Solution {
public:
int maximumSwap(int num) {
string str = to_string(num);
int res = num, n = str.size();
for (int i = ; i < n; ++i) {
for (int j = i + ; j < n; ++j) {
swap(str[i], str[j]);
res = max(res, stoi(str));
swap(str[i], str[j]);
}
}
return res;
}
};
下面这种解法是一种更优解，思路是这样的，由于希望置换后的数字最大，那么肯定最好的高位上的小数字和低位上的大数字进行置换，比如题目汇总的例子1。而如果高位上的都是大数字，像例子2那样，很有可能就不需要置换。所以需要找到每个数字右边的最大数字(包括其自身)，这样再从高位像低位遍历，如果某一位上的数字小于其右边的最大数字，说明需要调换，由于最大数字可能不止出现一次，这里希望能跟较低位的数字置换，这样置换后的数字最大，所以就从低位向高位遍历来找那个最大的数字，找到后进行调换即可。比如对于 1993 这个数：
1 9 9 3
9 9 9 3 (back数组)
9 9 1 3
我们建立好back数组后，从头遍历原数字，发现1比9小，于是从末尾往前找9，找到后一置换，就得到了 9913。
解法二：
class Solution {
public:
int maximumSwap(int num) {
string res = to_string(num), back = res;
for (int i = back.size() - ; i >= ; --i) {
back[i] = max(back[i], back[i + ]);
}
for (int i = ; i < res.size(); ++i) {
if (res[i] == back[i]) continue;
for (int j = res.size() - ; j > i; --j) {
if (res[j] == back[i]) {
swap(res[i], res[j]);
return stoi(res);
}
}
}
return stoi(res);
}
};
下面这种解法建了十个桶，分别代表数字0到9，每个桶存该数字出现的最后一个位置，也就是低位。这样从开头开始遍历数字上的每位上的数字，然后从大桶开始遍历，如果该大桶的数字对应的位置大于当前数字的位置，说明低位的数字要大于当前高位上的数字，那么直接交换这两个数字返回即可，其实核心思路跟上面的解法蛮像的，参见代码如下：
解法三：
class Solution {
public:
int maximumSwap(int num) {
string str = to_string(num);
vector<int> buckets(, );
for (int i = ; i < str.size(); ++i) {
buckets[str[i] - ''] = i;
}
for (int i = ; i < str.size(); ++i) {
for (int k = ; k > str[i] - ''; --k) {
if (buckets[k] <= i) continue;
swap(str[i], str[buckets[k]]);
return stoi(str);
}
}
return num;
}
};
我们也可以进一步的优化空间，实际上只关注两个需要交换的位置即可，即高位上的小数字和低位上的大数字，分别用 pos1 和 pos2 指向其位置，均初始化为 -1，然后用一个指针 mx 指向低位最大数字的位置，初始化为 n-1，然后从倒数第二个数字开始往前遍历，假如 str[i] 小于 str[mx]，说明此时高位上的数字小于低位上的数字，是一对儿潜在可以交换的对象（但并不保证上最优解），此时将 pos1 和 pos2 分别赋值为 i 和 mx；若 str[i] 大于 str[mx]，说明此时 str[mx] 不是低位最大数，将 mx 更新为 i。循环结束后，若 pos1 不为 -1，说明此时找到了可以交换的对象，而且找到的一定是最优解，直接交换即可，参见代码如下：
解法四：
class Solution {
public:
int maximumSwap(int num) {
string str = to_string(num);
int n = str.size(), mx = n - , pos1 = -, pos2 = -;
for (int i = n - ; i >= ; --i) {
if (str[i] < str[mx]) {
pos1 = i;
pos2 = mx;
} else if (str[i] > str[mx]) {
mx = i;
}
}
if (pos1 != -) swap(str[pos1], str[pos2]);
return stoi(str);
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/670
类似题目：
参考资料：
https://leetcode.com/problems/maximum-swap/
https://leetcode.com/problems/maximum-swap/discuss/107068/Java-simple-solution-O(n)-time
https://leetcode.com/problems/maximum-swap/discuss/107153/simple-c-using-stdstring-and-stdstoi
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- 树形DP+DFS序+树状数组 HDOJ 5293 Tree chain problem（树链问题）
- Asp.net下使用HttpModule模拟Filter，实现权限控制
- 46-df 显示磁盘空间的使用情况
- C++11 不抛异常的new operator
- js的事件属性方法一览表
- pop，墨刀，快现、justinmind 、Axure
- 老李分享：大数据测试中java和hadoop关系
- mysql常用的操作
- 分享两个细致、全面讲解Vue和React源码的链接
- Python IO编程
- 工具篇-Spark-Streaming获取kafka数据的两种方式（转载）
- 面试必问Elasticsearch倒排索引原理
- 微信、支付宝支付SDK
- 面试准备——（三）Selenium（1）基础问题及自动化测试
- (转载)Windows WMIC命令使用详解(附实例)
- 《算法》第二章部分程序 part 5
- Python基础【day03】：文件操作(六)
- Azure认知服务的实际应用-资讯采集推送
- 关于远程访问Oracle数据库的设置(共享数据库)
- Laravel源码解析--看看Lumen到底比Laravel轻在哪里