Leetcode(670) Maximum Swap

发表于 | 分类于

Description

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

1
2
3
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

1
2
3
Input: 9973
Output: 9973
Explanation: No swap.

Note:

  1. The given number is in the range [0, 108]

解法

思路：先找到每个位置对应的在他右边的最大的数，然后从高位起扫描数组，找到第一个存在右边比他大的数的位置，然后从数组尾部开始扫描，找到这个比他大的数，然后交换即可

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maximumSwap(int num) {
        char[] input = Integer.toString(num).toCharArray();
        char[] maxnum = new char[input.length - 1];
        if(input.length == 1){
            return Integer.parseInt(new String(input));
        }
        maxnum[maxnum.length - 1] = (char) Math.max(input[maxnum.length], input[maxnum.length - 1]);
        for (int i = maxnum.length - 2; i >= 0; i--) {
            maxnum[i] = (char) Math.max(input[i], maxnum[i + 1]);
        }
        for (int i = 0; i < maxnum.length; i++) {
            if (maxnum[i] > input[i]) {
                for (int j = input.length - 1; j > i; j--) {
                    if (input[j] == maxnum[i]) {
                        char tmp = input[j];
                        input[j] = input[i];
                        input[i] = tmp;
                        return Integer.parseInt(new String(input));
                    }
                }
            }
        }
        return Integer.parseInt(new String(input));
    }
}