LeetCode 刷题 [C++] 第670题.最大交换

本文主要是介绍LeetCode 刷题 [C++] 第670题.最大交换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。

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

注意:
给定数字的范围是 [0, 108]。

题目分析

从左向右查看num：

如果一个数字右边有比它大的数，则选择最大的数与之交换最优；
如果存在多个相同的最大数字，则选择最靠后的那个与之交换最优；
将右侧最大的数字越往左替换，数值约大；
如果没有比它大的，则无需交换。
因此，这个题目使用贪心算法来解决。

我们可以先将num数组转换成字符串s，然后对其进行对应处理：

1. 倒序遍历s， 同时维护最大数的下标max_idx。max_idx只在遇到比它大的数字时才更新，小于等于的数字不更新；
2. 如果遇到小于max_idx的值时，先不进行更新，先将当前值的位置保存到p和max_idx保存q中；
3. 继续向左遍历，如果再次遇到小于max_idx位置的值，则更新p和q.
4. 遍历结束后，交换p和q对应位置的数字，如果无需交换，则直接返回num。

Code

class Solution {
public:int maximumSwap(int num) {string s = to_string(num);int n = s.length();int max_idx = n - 1;int p = -1, q;for (int i = n - 2; i >= 0; --i) {if (s[i] > s[max_idx]) {max_idx = i;} else if (s[i] < s[max_idx]) {p = i;q = max_idx;}}if (-1 == p) {return num;}swap(s[p], s[q]);return stoi(s);}
};

这篇关于LeetCode 刷题 [C++] 第670题.最大交换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---