亲宝软件园·资讯

展开

Java C++ 算法最大交换

AnjaVon 人气:0

题目要求

思路:模拟

Java

class Solution {
    public int maximumSwap(int num) {
        List<Integer> list = new ArrayList<>();
        while (num != 0) {
            list.add(num % 10);
            num /= 10;
        }
        int n = list.size(), res = 0;
        int[] idx = new int[n];
        for (int i = 0, j = 0; i < n; i++) {
            if (list.get(i) > list.get(j)) // 严格大于
                j = i;
            idx[i] = j;
        }
        for (int i = n - 1; i >= 0; i--) { // 高位开始
            if (list.get(idx[i]) != list.get(i)) {
                int tmp = list.get(idx[i]);
                list.set(idx[i], list.get(i));
                list.set(i, tmp);
                break;
            }
        }
        for (int i = n - 1; i >= 0; i--)
            res = res * 10 + list.get(i);
        return res;
    }
}

C++

class Solution {
public:
    int maximumSwap(int num) {
        vector<int> list;
        while (num != 0) {
            list.emplace_back(num % 10);
            num /= 10;
        }
        int n = list.size(), res = 0;
        int idx[n];
        for (int i = 0, j = 0; i < n; i++) {
            if (list[i] > list[j]) // 严格大于
                j = i;
            idx[i] = j;
        }
        for (int i = n - 1; i >= 0; i--) { // 高位开始
            if (list[idx[i]] != list[i]) {
                int tmp = list[idx[i]];
                list[idx[i]] =list[i];
                list[i] = tmp;
                break;
            }
        }
        for (int i = n - 1; i>= 0; i--)
            res = res * 10 + list[i];
        return res;
    }
};

Rust

impl Solution {
    pub fn maximum_swap(num: i32) -> i32 {
        let mut list = vec![];
        let mut res = num;
        while (res != 0) {
            list.push(res % 10);
            res /= 10;
        }
        let n = list.len();
        let mut idx = vec![0; n];
        let mut j = 0;
        for i in 0..n {
            if list[i] > list[j] {
                j = i;
            }
            idx[i] = j;
        }
        for k in n-1..0 {
            if list[idx[k]] != list[k] {
                list.swap(idx[k], k);
                break;
            }
        }
        for l in n-1..0 {
            res = res * 10 + list[l];
        }
        res
    }
}

加载全部内容

相关教程
猜你喜欢
用户评论