题目
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:
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973
Output: 9973
Explanation: No swap.
分析
给定一个非负数,得到交换一次所能得到的最大的值。
基本思想就是把大数从右侧换到左侧来。有两种方法：
- 两次扫描，第一次扫描从右往左记录当前最大值和最大值所在位置，第二次扫描从左往右找到当前最大值和当前值不相等的数，因为有最大值所在位置，可以交换
index 3 2 1 0 3 2 1 0
nums 2 7 3 6 9 9 7 3
max 7 7 6 6 9 9 7 3
maxIndex 2 2 0 0 3 2 1 0
找到2和7不相同，交换第2个位置和第3个位置，如果没有则不用交换。
- 两次扫描，第一次用桶记录下上次（0-9）这个数字出现的位置，第二次扫描从记录中找比当前数大的值是否在其右侧出现了，出现了则交换（选最大可能的）。
代码
//方法1
public int maximumSwap(int num) {
if(num <= 10) return num;
List<Integer> nums = new ArrayList<>();
List<Integer> maxs = new ArrayList<>();
List<Integer> indexs = new ArrayList<>();
int max = -1, index = -1, i = -1;
while(num != 0){
int m = num % 10;
num /= 10;
i ++;
nums.add(m);
if(m > max){
max = m;
index = i;
}
maxs.add(max);
indexs.add(index);
}
for(int k = nums.size() - 1; k >= 0; --k){
if(!nums.get(k).equals(maxs.get(k))){
int temp = nums.get(k);
nums.set(k, maxs.get(k));
nums.set(indexs.get(k), temp);
break;
}
}
int res = 0;
for(int k = nums.size() - 1; k >= 0; --k){
res = res * 10 + nums.get(k);
}
return res;
}
//方法2
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int[] buckets = new int[10];
for (int i = 0; i < digits.length; i++) {
buckets[digits[i] - '0'] = i;
}
for (int i = 0; i < digits.length; i++) {
for (int k = 9; k > digits[i] - '0'; k--) {
if (buckets[k] > i) {
char tmp = digits[i];
digits[i] = digits[buckets[k]];
digits[buckets[k]] = tmp;
return Integer.valueOf(new String(digits));
}
}
}
return num;
}
