最大交换Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给定一个非负整数,你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。
示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。
注意:
- 给定数字的范围是 [0, 108]
# 思路
//倒过来寻找,当前位置往右,最大的数的下标
//正序遍历,找到第一个不是最大的数,将该位置和右边最大数换位置
# 解法
class Solution {
public int maximumSwap(int num) {
if(num == 0)
return 0;
char[] chars = String.valueOf(num).toCharArray();
int[] maxIndex = new int[chars.length];
int max = chars.length - 1;
//倒过来寻找,当前位置往右,最大的数的下标
for(int j = chars.length - 1;j>=0;j--){
if(chars[j] - '0' > chars[max] - '0'){
max = j;
}
maxIndex[j] = max;
}
//正序遍历,找到第一个不是最大的数,将该位置和右边最大数换位置
for(int i = 0;i<chars.length;i++){
int iValue = chars[i] - '0';
int maxValue = chars[maxIndex[i]] - '0';
if(maxValue != iValue){
chars[i] = (char) (maxValue + '0');
chars[maxIndex[i]] = (char) (iValue + '0');
break;
}
}
return Integer.parseInt(new String(chars));
}
}
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
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
# 总结
- 分析出几种情况,然后分别对各个情况实现