670.最大交换

链接：670.最大交换
难度：Medium
标签：贪心、数学
简介：给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

题解 1 - cpp

• 编辑时间：2022-09-13
• 内存消耗：5.7MB
• 编程语言：cpp
• 解法介绍：寻找是否存在比当前值大的低位数。

class Solution {
public:
    int maximumSwap(int num) {
        int list[10] = {0}, list_len = 0;
        for (; num; num /= 10) list[list_len++] = num % 10;
        for (int i = list_len - 1; i > 0; i--) {
            int max_idx = i - 1;
            for (int j = i - 1; j >= 0; j--) max_idx = list[max_idx] > list[j] ? max_idx : j;
            if (list[max_idx] > list[i]) {
                swap(list[max_idx], list[i]);
                break;
            }
        }
        int ans = 0;
        for (int i = list_len - 1; i >= 0; i--) ans = ans * 10 + list[i];
        return ans;
    }
};

题解 2 - python

• 编辑时间：2024-01-22
• 执行用时：42ms
• 内存消耗：16.49MB
• 编程语言：python
• 解法介绍：贪心。

class Solution:
    def maximumSwap(self, num: int) -> int:
        arr = [[] for _ in range(10)]
        lnum = list(int(c) for c in str(num))
        for i in range(len(lnum)): arr[lnum[i]].append(i)
        swap = False
        for i in range(len(lnum)):
            for num in range(9, -1, -1):
                if lnum[i] >= num: break
                while arr[num] and arr[num][-1] < i: arr[num].pop()
                if arr[num]:
                    lnum[i], lnum[arr[num][-1]] = lnum[arr[num][-1]], lnum[i]
                    swap = True
            if swap: break
        return reduce(lambda sum, num: sum * 10 + num, lnum, 0)