05 August 2008
给一个整数，交换两个digists一次，使数最大
注意负数的情况
Example 1:
1
2
3
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
1
2
3
Input: num = 9973
Output: 9973
Explanation: No swap.
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
/*
使用 buckets 来记录数字 0 ~ 9 的最后出现位置。
从左到右遍历num的数字，对于每个位置，我们查找是否在之后的位置中存在一个比它更大的数（从 9 一直找到当前位置的数字大小）。我们也需要确保这个更大的数字的位置 是 位于当前位置 之后的。如果找到了，我们就可以交换这两个数字的位置，返回结果。
*/
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--) {// k需要比数字digits[i]大
if (buckets[k] > i) {//如果k的位置在i后面
char temp = digits[i];
digits[i] = digits[buckets[k]];
digits[buckets[k]] = temp;
return Integer.valueOf(new String(digits));
}
}
}
return num;
}
/*另外一个思路
如果有一个低位数字比高位数字要大，那么交换它们肯定能使得当前数变得更大。为了在交换后得到最大的数，不但需要：与可能的最高位交换，也需要：确保你交换到最高位的数要尽量足够大。
算法如下:
从最低位一直遍历到最高位，存储迄今为止最大的数字。
如果当前数字比迄今为止最大的数字小，那么存储swap索引：当前数字的索引 和 迄今为止最大数字的索引。
如果当前数字比迄今为止最大的数字大，那么重置 迄今为止最大的数字。
最后，交换之前存储的两个swap索引。重新计算数字。
maxSeen ：迄今为止最大的数字。
maxIdx ：迄今为止最大数字的索引。
power ：当前访问数字的索引
swapIdx's ：需要被交换的数字 的索引
public int maximumSwap(int num) {
int maxSeen = 0, maxIdx = -1, power = 0, swapIdx1 = 0, swapIdx2 = 0;
List<Integer> list = new ArrayList<>();
while(num > 0){
int digit = num % 10;
list.add(digit);
if(maxSeen > digit){
swapIdx1 = power;
swapIdx2 = maxIdx;
}
else if(digit > maxSeen){
maxSeen = digit;
maxIdx = power;
}
num = num/10;
power++;
}
Collections.swap(list, swapIdx1, swapIdx2);
int result = 0;
for(int i = 0; i < list.size(); i++){
result += (int)(Math.pow(10, i) * list.get(i));
}
return result;
}
*/
}