侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-09-13 / 0 评论 / 0 点赞 / 38 阅读 / 702 字 / 正在检测是否收录...

题目

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;
    }
};
0

评论区