✨今日算法一题
文章目录
题目描述
思路详解
思路一：暴力法
暴力法就比较好想了，因为数字最多只有8位，因此只有28个可用的交换。
我们首先将数字转换为列表，每次进行交换，与原始数据进行比较，如果原始的大就保存，否则就保留原始的。
思路二：贪心法
本算法运用了贪心的思想，大大缩短了时间复杂度。
首先将计算 last[d] = i，最后一次出现的数字 d（如果存在）的索引 i。
然后，从左到右扫描数字时，如果将来有较大的数字，将用最大的数字交换；如果有多个这样的数字，我们将用最开始遇到的数字交换。
代码与结果
一：暴力法
public class Solution { public int maximumSwap(int num) { String s = String.valueOf(num); int len = s.length(); char[] charArray = s.toCharArray(); int max = num; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { swap(charArray, i, j); max = Math.max(max, Integer.parseInt(new String(charArray))); swap(charArray, i, j); } } return max; } private void swap(char[] charArray, int index1, int index2) { char temp = charArray[index1]; charArray[index1] = charArray[index2]; charArray[index2] = temp; } }
二：贪心法
public class Solution { public int maximumSwap(int num) { String s = String.valueOf(num); int len = s.length(); char[] charArray = s.toCharArray(); // 记录每个数字出现的最后一次出现的下标 int[] last = new int[10]; for (int i = 0; i < len; i++) { last[charArray[i] - '0'] = i; } // 从左向右扫描，找到当前位置右边的最大的数字并交换 for (int i = 0; i < len - 1; i++) { // 找最大，所以倒着找 for (int d = 9; d > charArray[i] - '0'; d--) { if (last[d] > i) { swap(charArray, i, last[d]); // 只允许交换一次，因此直接返回 return Integer.parseInt(new String(charArray)); } } } return num; } private void swap(char[] charArray, int index1, int index2) { char temp = charArray[index1]; charArray[index1] = charArray[index2]; charArray[index2] = temp; } }
✨总结
今日的题是贪心算法的实际应用，在对于排序组合等方面，贪心算法表现比较优异，小伙伴们多多使用练习就可以熟练的，加油！！！
