題目
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.
分析
給定一個(gè)非負(fù)數(shù),得到交換一次所能得到的最大的值法竞。
基本思想就是把大數(shù)從右側(cè)換到左側(cè)來(lái)撵渡。有兩種方法：
- 兩次掃描雷则，第一次掃描從右往左記錄當(dāng)前最大值和最大值所在位置，第二次掃描從左往右找到當(dāng)前最大值和當(dāng)前值不相等的數(shù)万伤，因?yàn)橛凶畲笾邓谖恢弥匣冢梢越粨Q
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個(gè)位置和第3個(gè)位置壕翩，如果沒(méi)有則不用交換。
- 兩次掃描傅寡，第一次用桶記錄下上次（0-9）這個(gè)數(shù)字出現(xiàn)的位置放妈，第二次掃描從記錄中找比當(dāng)前數(shù)大的值是否在其右側(cè)出現(xiàn)了，出現(xiàn)了則交換（選最大可能的）荐操。
代碼
//方法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;
}
