【暴力, 贪心, 模拟】最大交换

题目

670. 最大交换

---

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

示例 1 :

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

示例 2 :

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

注意:

1. 给定数字的范围是 [0, 10^8]

解题

方法一：暴力 枚举

思路

枚举所有两个数字交换后能形成的整数结果，维护其中最大的返回即可。

代码

class Solution {
    public int maximumSwap(int num) {
        char[] chsNum = String.valueOf(num).toCharArray();
        int n = chsNum.length, maxNum = num;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(chsNum, i, j);
                maxNum = Math.max(maxNum, Integer.parseInt(String.valueOf(chsNum)));
                swap(chsNum, i, j);
            }
        }
        return maxNum;
    }

    void swap(char[] arr, int i, int j) {
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

class Solution {
public:
    int maximumSwap(int num) {
        string str_num = to_string(num);
        int n = str_num.length();
        int max_num = num;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(str_num[i], str_num[j]);
                max_num = max(max_num, stoi(str_num));
                swap(str_num[i], str_num[j]);
            }
        }
        return max_num;
    }
};

方法二：贪心算法 模拟

思路

我们需要找到两个数位：

1. 第一个数位尽可能靠左，这样能保证另一个数位能替换到较高的数位以获得较大的数字。
2. 第二个数位尽可能大且尽可能靠右。
   • 尽可能大是要保证数字替换过去后获得尽可能大的数字。
     比如 98368 ：
     • 第一个数位找到 3 时，第一个比它大的右边的数是 6 ，这样替换后是 98638。
     • 不如找比 6 更大的 8 替换后是 98863 比刚才得到的结果更大。
   • 尽可能靠右是为了用较低位的数字换高位，从而不让该低位的数字被替换后损失太严重。
     比如 1993：
     • 第一个数位找到 1 时，有两个比它尽可能大的数字 9，如果用第一个 9 替换后是 9193。
     • 不如用第二个 9 替换后是 9913 越低的位损失越小，得到的结果就越大。

代码

class Solution {
    public int maximumSwap(int num) {
        char[] chsNum = String.valueOf(num).toCharArray();
        int n = chsNum.length;
        for (int i = 0; i < n; ++i) {
            int mx = i;
            for (int j = i; j < n; ++j) {
                if (chsNum[j] >= chsNum[mx]) mx = j;
            }
            if (mx != i && chsNum[mx] != chsNum[i]) {
                char tmp = chsNum[i];
                chsNum[i] = chsNum[mx];
                chsNum[mx] = tmp;
                return Integer.parseInt(String.valueOf(chsNum));
            }
        }
        return num;
    }
}

class Solution {
public:
    int maximumSwap(int num) {
        string str_num = to_string(num);
        int n = str_num.length();
        for (int i = 0; i < n - 1; ++i) {
            int mx = i;
            for (int j = i; j < n; ++j) {
                if (str_num[j] >= str_num[mx]) mx = j;
            }
            if (mx != i && str_num[i] != str_num[mx]) {
                swap(str_num[i], str_num[mx]);
                return stoi(str_num);
            }
        }
        return num;
    }
};