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


    • 🧛‍♂️个人主页:杯咖啡
    • 💡进步是今天的活动,明天的保证!
    • ✨目前正在学习:SSM框架,算法刷题
    • 🙌牛客网,刷算法过面试的神级网站,用牛客你也牛。 👉免费注册和我一起学习刷题👈
    • 🐳希望大家多多支持🥰一起进步呀!
    • 😎The supreme happiness of life is the conviction that we are loved.
      人生最大的幸福是坚信有人爱我们。-《巴黎圣母院》

    ✨今日算法一题

    最大交换



    最大交换

    题目描述

    在这里插入图片描述

    思路详解

    思路一:暴力法

    暴力法就比较好想了,因为数字最多只有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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    在这里插入图片描述

    二:贪心法

    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;
        }
    }
    
    • 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
    • 30
    • 31
    • 32
    • 33

    在这里插入图片描述


    ✨总结

    今日的题是贪心算法的实际应用,在对于排序组合等方面,贪心算法表现比较优异,小伙伴们多多使用练习就可以熟练的,加油!!!

    原创不易,还希望各位大佬支持一下 \textcolor{blue}{原创不易,还希望各位大佬支持一下} 原创不易,还希望各位大佬支持一下

    点赞,你的认可是我创作的动力! \textcolor{green}{点赞,你的认可是我创作的动力!} 点赞,你的认可是我创作的动力!

    收藏,你的青睐是我努力的方向! \textcolor{green}{收藏,你的青睐是我努力的方向!} 收藏,你的青睐是我努力的方向!

    评论,你的意见是我进步的财富! \textcolor{green}{评论,你的意见是我进步的财富!} 评论,你的意见是我进步的财富!

  • 相关阅读:
    TypeScript 笔记:变量声明、类型断言、变量作用域
    使用PostMan Canary测试受Identity Server 4保护的Web Api
    仅用CSS几步实现赛博朋克2077风格视觉效果
    易优cms小程序插件升级到2.1版本
    【React】React 基础
    基于猕猴感觉运动皮层Spike信号的运动解码分析不同运动参数对解码的影响
    ubuntu apt-get update 失败 server certificate verification failed
    HDLbits exercises 5 (BASIC GATES节选题)
    SAP各模块优缺点和发展简析
    Java - Hashtable原理分析
  • 原文地址:https://blog.csdn.net/muzi_longren/article/details/125886462