本文主要是介绍leetcode - 670. Maximum Swap【贪心策略 + 备忘录】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
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, 108]
分析及解答
- 高位的数字变大，对于整个数的影响是很大的。
- 同时，交换时，应将对于对于低位的影响最小化。（交换导致低位变小）
public int maximumSwap(int num) {if (num <= 10) {return num;}//转成字符串，更方便处理。char[] strArr = String.valueOf(num).toCharArray();char max = '0';int[] dp = new int[strArr.length];//dp[i]存储 i 后面的最大的数字。dp[strArr.length - 1] = strArr.length - 1;for (int i = strArr.length - 1; i >= 0; i--) {if (max < strArr[i]) { // 不选择等于。（只有比其大的数才有交换意义）max = strArr[i];dp[i] = i;} else {dp[i] = dp[i-1];}}for (int i = 0; i < dp.length; i++) {if (dp[i] > i && strArr[i] != strArr[dp[i]]) {char tmp = strArr[i];strArr[i] = strArr[dp[i]];strArr[dp[i]] = tmp;break; //忘记加，导致bug.}}return Integer.valueOf(new String(strArr));}
这篇关于leetcode - 670. Maximum Swap【贪心策略 + 备忘录】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
