力扣leetcode 670. 最大交换

题目链接与描述

https://leetcode.cn/problems/maximum-swap/

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。
示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。
注意:

给定数字的范围是 [0, 10^8]

关键词： 数值交换 贪心

方法一：

运行截图

代码

使数字最大，很容易想到把数值大的往前排，数值小的往后排， 最暴力的解法： 我们要最大，那就把数字最大的排前面，保证前面的都是最大的,把数字遍历一遍，取后n位最大的出来对比即可

转换思路，因为最大的数一定时按大的前，小的在后;且我们只能拿一个，所以只需要找到最大的那个数，比前方小的靠前的值交换即可

	public int maximumSwap(int num) {
		char[] charArray = String.valueOf(num).toCharArray();
		int n = charArray.length;
		int maxIdx = n - 1;
		int idx1 = -1, idx2 = -1;
		for (int i = maxIdx; i >= 0; i--) {
			if (charArray[i] > charArray[maxIdx]) {
				maxIdx = i;
			} else if (charArray[i] < charArray[maxIdx]) {
				idx1 = i;
				idx2 = maxIdx;
			}
		}
		if (idx1 >= 0) {
			swap(charArray, idx1, idx2);
			return Integer.parseInt(new String(charArray));
		} else {
			return num;
		}
	}
	public void swap(char[] charArray, int i, int j) {
		char temp = charArray[i];
		charArray[i] = charArray[j];
		charArray[j] = temp;
	}



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

结尾

欢迎评论区交流，每日打卡，冲冲冲！！！