Java?C++?算法題解拓展leetcode670最大交換示例

更新時間：2022年09月14日 08:59:06 作者：AnjaVon

這篇文章主要介紹了Java?C++算法題解拓展leetcode670最大交換示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目要求

思路：模擬

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

時間復雜度：O(log ?num)
空間復雜度：O(log ?num)

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

時間復雜度：O(log? num)
空間復雜度：O(log ?num)

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