【算法刷题】—7.20贪心算法的应用与暴力方法的对比体验

2022-10-08 156

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： ✨今日算法一题最大交换

✨今日算法一题

最大交换

文章目录

题目描述

思路详解

思路一：暴力法

暴力法就比较好想了，因为数字最多只有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;
    }
}