Medium
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.
Note:
The given number is in the range [0, 10^8]
这道题一开始想不知道该按什么顺序去换，没有很清晰的思路。但这种题通常有规律可循，不可能给你一个很天方夜谭的换法，那就一个一个的换呗。比如这里，每个数字跟它后面的数字先比较，如果比后面的数字小，那就互换，否则继续。注意每次换完还要换回来，类似于DFS里的backtracking. 这样在记录一个max随时更新，最后遍历完就可以得到最大的值。要注意一下StringBuilder的API, 以及String和int互相转换的方法等等。
class Solution {
public int maximumSwap(int num) {
String str = "" + num;
StringBuilder sb = new StringBuilder(str);
int max = Integer.MIN_VALUE;
for (int i = 0; i < sb.length(); i++){
for (int j = i + 1; j < sb.length(); j++){
if (sb.charAt(i) < sb.charAt(j)){
swap(sb, i, j);
if (Integer.parseInt(sb.toString()) > max){
max = Integer.parseInt((sb.toString()));
}
swap(sb, i, j);
}
}
}
if (max == Integer.MIN_VALUE){
return num;
}
return max;
}
private void swap(StringBuilder sb, int i, int j){
char temp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(j));
sb.setCharAt(j, temp);
}
}
