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:

  1. 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 = 0; i < n; ++i) {
            for (int j = i + 1; 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() - 2; i >= 0; --i) {
            back[i] = max(back[i], back[i + 1]);
        }
        for (int i = 0; i < res.size(); ++i) {
            if (res[i] == back[i]) continue;
            for (int j = res.size() - 1; 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(10, 0);
        for (int i = 0; i < str.size(); ++i) {
            buckets[str[i] - '0'] = i;
        }
        for (int i = 0; i < str.size(); ++i) {
            for (int k = 9; k > str[i] - '0'; --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 - 1, pos1 = -1, pos2 = -1;
        for (int i = n - 2; i >= 0; --i) {
            if (str[i] < str[mx]) {
                pos1 = i;
                pos2 = mx;
            } else if (str[i] > str[mx]) {
                mx = i;
            }
        }
        if (pos1 != -1) swap(str[pos1], str[pos2]);
        return stoi(str);
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/670

 

类似题目:

Create Maximum Number

 

参考资料:

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

https://leetcode.com/problems/maximum-swap/discuss/107084/C%2B%2B-3ms-O(n)-time-O(n)-space-DP-solution

https://leetcode.com/problems/maximum-swap/discuss/107073/C%2B%2B-one-pass-simple-and-fast-solution%3A-1-3ms-O(n)-time

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation