Leetcode 670 最大交换 // 洛七的摸鱼池塘

670.最大交换

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

示例 1:

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

示例 2:

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

注意:

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

解答

本题的难度是 Medium.

首先很自然的想法，当然是越高位的被换成越大越好, 因此我们从左到右遍历, 对于每一位来看, 这一位的右边有没有更大的, 如果有就把右边最大的和当前位进行换, 如果没有, 说明当前遍历过的数字已经是最大的了, 就要看看后面的了. 当然右边同时有两个是最大的, 那么当然是选位更小的那个数字, 因此从右向左遍历.

比如: 96177, 9 的右边没有比 9 更大的了, 因此跳到 6, 右边最大的为 7, 因此我们要找最大的应该用最低位, 即个位的 7. 得到结果, 97176。

代码如下:

class Solution {
    public int maximumSwap(int num) {
        String s = Integer.toString(num);
        for (int i = 0; i < s.length()-1; i++) {
            char tempPre = s.charAt(i);
            int record = s.length()-1;
            char temp = s.charAt(record);

            for (int j = s.length()-1; j >i; j--) {
                if (s.charAt(j)>temp){
                    temp = s.charAt(j);
                    record = j;
                }

            }
            if (tempPre < temp && i+1 <= s.length()){
                return Integer.valueOf(s.substring(0,i) + temp+s.substring(i+1,record)+tempPre+s.substring(record+1,s.length()));
            }
        }
        return num;
    }
}

然后用时 11ms, 太抽象了, 只能击败 3.08% 的用户, 应该是因为反复 substring, 且 charAt, 用 String 相加进行字符串拼接字符串.

因此为了解决这个问题, 进行了简单的代码修改.

class Solution {
    public int maximumSwap(int num) {

        char[] chars = String.valueOf(num).toCharArray();
        int n = chars.length;
        for (int i = 0; i < n-1; i++) {
            char tempPre = chars[i];
            int record = n-1;
            char temp = chars[record];

            for (int j = n-1; j >i; j--) {
                if (chars[j]>temp){
                    temp = chars[j];
                    record = j;
                }

            }
            if (tempPre < temp){
                chars[i] = temp;
                chars[record] = tempPre;
                return Integer.valueOf(String.valueOf(chars));
            }
        }
        return num;
    }
}

这样用时就 0ms 了, 不过这题有个问题就是最大数值太短了, 导致原本可以用 dp 的, 但是没用就够了, 因为太短了, 如果数字是几十位长的用 dp 应该才会有比较明显的时间效率差. 上面的代码时间复杂度应该是 O(n^2), 当然这里的 n 指的是 num 的长度

但是还是写了用 dp 的代码, 因为我不怎么会写:

class Solution {
    public int maximumSwap(int num) {

        char[] chars = String.valueOf(num).toCharArray();
        int n = chars.length;
        // 存当前位到最右边最大的是谁
        char[] dp = new char[n];
        // 这个存这个最大位出现最右的位置是哪一个
        int[] dpIndex = new int[n];
        dp[n-1] = chars[n-1];
        dpIndex[n-1] = n-1;
        for (int i = n-2; i >= 0 ; i--) {
            if (chars[i] > dp[i+1] ){
                dp[i] = chars[i];
                dpIndex[i] = i;
            } else {
                dp[i] = dp[i+1];
                dpIndex[i] = dpIndex[i+1];
            }
        }
        for (int i = 0; i < n-1; i++) {
            if (chars[i] < dp[i+1]){
                char temp = chars[i];
                chars[i] = dp[i+1];
                chars[dpIndex[i+1]] = temp;
                break;
            }
        }
        return Integer.valueOf(String.valueOf(chars));
    }
}

这个代码的时间复杂度是 O(n), 自然执行也是 0ms.