LeetCode 670: 最大交换

[guodongxiaren]

https://leetcode-cn.com/problems/maximum-swap/

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

示例 1 :

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

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

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

[guodongxiaren]

注意：

• 数字位存在重复

解题思路： 将数字位逆序排序。和原数一一对比。找到第一组不相同的数字，称之为互为姘头。原数该位小，排序数该位大。 将原数中该数字和从右到左找到的其姘头数。（存在多个相同姘头数的情况，需要找最靠右的）

class Solution {
public:
    int maximumSwap(int num) {
        vector<int> digits;
        int n = num;
        while (n) {
            digits.push_back(n%10);
            n /= 10;
        }
        reverse(digits.begin(), digits.end());

        auto old = digits;

        sort(digits.begin(), digits.end(), greater<int>());

        int size = digits.size();

        int big = -1;
        int small = -1;
        int si = -1;
        for (int i = 0; i < size; ++i) {
            if (digits[i] != old[i]) {
                big = digits[i];
                small = old[i];
                si = i;
                break;
            }
        }
        int t = big;
        for (int i = size-1; i >=0; --i) {
            if (big != -1 && old[i] == big) {
                old[i] = small;
                big = -1;
            }
            if (i == si) {
                old[i] = t;
            }
        }

        int d = 0;
        for (int i: old) {
            d = d*10 +i;
        }

        return d;
    }
};

[guodongxiaren]

优化点：上例为vector存储digits，可以变换成string。省去复杂度构造vector，然后reserve的过程。也可以通篇用string不用vector。

class Solution {
public:
    int maximumSwap(int num) {
        string str = to_string(num);

        vector<int> digits(str.size());
        transform(str.begin(), str.end(), digits.begin(), [](char a){return a-'0';});

        auto old = digits;

        sort(digits.begin(), digits.end(), greater<int>());

        int size = digits.size();

        int big = -1;
        int small = -1;
        int si = -1;
        for (int i = 0; i < size; ++i) {
            if (digits[i] != old[i]) {
                big = digits[i];
                small = old[i];
                si = i;
                break;
            }
        }
        int t = big;
        for (int i = size-1; i >=0; --i) {
            if (big != -1 && old[i] == big) {
                old[i] = small;
                big = -1;
            }
            if (i == si) {
                old[i] = t;
            }
        }

        int d = 0;
        for (int i: old) {
            d = d*10 +i;
        }

        return d;
    }
};