贪心算法专题(一)

ops/2024/10/20 11:53:27/

目录

1、算法>贪心算法简介

1.1 什么是算法>贪心算法

1.2 算法>贪心算法的特点

1.3 算法>贪心算法的学习方向

leetcode%E3%80%91-toc" style="margin-left:0px;">2、算法应用【leetcode】

2.1 题一：柠檬水找零

2.1.1 算法原理

2.1.2 算法代码

2.2 题二：将数组和减半的最少操作次数

 2.2.1 算法原理

2.2.2 算法代码

2.3 题三：最大数

2.3.1 算法原理

2.3.2 算法代码

2.4 题四：摆动序列

2.4.1 算法原理

2.4.2 算法代码

2.5 题五：最长递增子序列

2.5.1 算法原理1——记忆化搜索

2.5.2 算法代码1——记忆化搜索

2.5.3 算法原理2——动态规划

2.5.4 算法代码2——动态规划

2.5.5 算法原理3——贪心+二分【最优解】

2.5.6 算法代码3——贪心+二分【最优解】

1、算法>贪心算法简介

1.1 什么是算法>贪心算法

算法>贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。在每一步选择中都采取当前状态下最优的选择，以期望达到全局最优解的算法策略‌。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

算法>贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

算法>贪心算法的核心就是：贪心策略。

而贪心策略就是由：局部最优解 推算出 全局最优解。

  1. 将解决问题的分为若干步，逐步击破
  2. 解决每一步时，选择当前步“最优的”解法
  3. “希望”得到全局最优解

1.2 算法>贪心算法的特点

我们可能是猜的、蒙的、靠直觉想出的贪心策略，所以贪心策略的正确性的不确定的。

贪心策略的提出：

  1. 算法>贪心算法和我们之前所学到的算法不同，贪心策略的提出是没有任何固定的模版或者标准的
  2. 每一道题的贪心策略都是不同的

贪心策略的正确性：

  1. 贪心策略可能是错误的
  2. 贪心策略需要各种数学方法的证明

1.3 算法>贪心算法的学习方向

由于每一道题的贪心策略都可能不同，所以即使我们做了几十道贪心题后，再面对对于一道新贪心题时，也可能会没有任何的思路。所以遇到不会的贪心题是很正常的，我们要把心态放平。

  1. 在前期学习时，将每道题的贪心策略当做经验来吸收，扩大对贪心策略的认知。
  2. 不用纠结别人的贪心策略是怎么想出的，想不出来很正常，我们当做经验把策略吸收即可。

leetcode%E3%80%91">2、算法应用【leetcode】

2.1 题一：柠檬水找零

. - 力扣（LeetCode）

2.1.1 算法原理

 对于5元和10元的找零策略是固定的，给20元找零时有两种策略：要么找三张5元；要么找一张5元和一张10元。

经过分析：5元的用处更多(给10元找零时要用)，所以要尽可能的保留5元。

故，贪心策略为：给20元找一张5元和一张10元；当10元不存在时才找三张5元。

2.1.2 算法代码

java">class Solution {public boolean lemonadeChange(int[] bills) {//<金额, 个数>int five = 0, ten = 0;if(bills[0] != 5) return false;for(int i = 0; i < bills.length; i++) {if(bills[i] == 5) five++;else if(bills[i] == 10) {if(five == 0) return false;five--; ten++;}else {if(five == 0) {return false;}else if(ten != 0) {//贪心ten--;five--;}else {if(five < 3) return false;five -= 3;}}}return true;}
}

2.2 题二：将数组和减半的最少操作次数

. - 力扣（LeetCode）

 2.2.1 算法原理

策略：贪心+大根堆

  1. 因为求使数组减半的最小的操作次数，
  2. 根据贪心策略，每次将数组中最大的元素进行减半操作，这样可使得操作次数最少。
  3. 循环这个过程，直至将数组和减半。

2.2.2 算法代码

java">class Solution {public int halveArray(int[] nums) {double sum = 0;//建大堆PriorityQueue<Double> queue = new PriorityQueue<>((o1,o2) -> o2.compareTo(o1));for (int i = 0; i < nums.length; i++) {sum += nums[i];queue.offer((double)nums[i]);}sum /= 2;int count = 0;while (sum > 0) {double peek = queue.poll();sum -= peek / 2;queue.offer(peek / 2);count++;}return count;}
}

2.3 题三：最大数

. - 力扣（LeetCode）

2.3.1 算法原理

本质：确定数组中元素的先后顺序（谁在前，谁在后）

核心：修改sort方法的排序规则 -> 进行元素拼接后的比较，将拼接后的较大的元素放在前面。

优化：使用字符串进行拼接

2.3.2 算法代码

java">class Solution {public String largestNumber(int[] nums) {String[] strs = new String[nums.length];for (int i = 0; i < nums.length; i++)strs[i] = nums[i] + "";Arrays.sort(strs, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));StringBuffer sb = new StringBuffer();for (String str : strs)sb.append(str);if (sb.charAt(0) == '0')return "0";return sb.toString();}
}

2.4 题四：摆动序列

. - 力扣（LeetCode）

2.4.1 算法原理

画出数组元素值的折线图，可以发现每次选取极值点可以使摆动序列的长度最大。

  • 贪心策略：选取折线图的极值点，计算极值点的个数。
  • 为什么该策略为贪心策略呢？——因为选取极大值或极小值，在下次选取元素时(满足摆动序列)会有更多的选择性（贪心策略），不会漏掉数据。

2.4.2 算法代码

java">class Solution {int left;//左侧的增减性int ret;public int wiggleMaxLength(int[] nums) {for(int i = 0; i < nums.length - 1; i++) {//右侧的增减性int right = nums[i + 1] - nums[i];//右侧元素与当前元素相同if(right == 0) continue;//极值点if(right * left <= 0) ret++;   left = right;}//加上最后一个节点return ret + 1;}
}

2.5 题五：最长递增子序列

. - 力扣（LeetCode）

2.5.1 算法原理1——记忆化搜索

算法核心：

  • dfs当前元素(pos位置)后面位置的元素（要求：nums[pos] < nums[后面序列]），寻找出最长递增子序列的长度，再加一(算上当前节点)，就是以当前位置为起点的最长递增子序列的长度。

备忘录优化（记忆化搜索）：

  • 使用memo数组存储以该位置为起点的最长递增子序列的长度。

2.5.2 算法代码1——记忆化搜索

java">class Solution {//记忆化搜索int ret = 1;int path;int[] memo;public int lengthOfLIS(int[] nums) {memo = new int[nums.length];int ret = 0;for(int i = 0; i < nums.length; i++) {ret = Math.max(ret, dfs(nums, i));}return ret;}public int dfs(int[] nums, int pos) {int ret = 1;if(memo[pos] != 0) return memo[pos];for(int i = pos + 1; i < nums.length; i++) {if(nums[i] > nums[pos]) {ret = Math.max(ret, dfs(nums, i) + 1);}}memo[pos] = ret;return ret;}
}

2.5.3 算法原理2——动态规划

算法核心：

  • 状态表示(dp[i])：以当前位置为结尾的最长递增子序列的长度
  • 状态转移方程：dp[i]=max(dp[j] + 1)【要求：(j < i && nums[j] < nums[i])】

2.5.4 算法代码2——动态规划

java">class Solution {//动态规划public int lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];Arrays.fill(dp, 1);for(int i = 0; i < n; i++) {for(int j = i - 1; j >= 0; j--) {if(nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}}int max = 0;for(int x : dp) max = Math.max(max, x);return max;}
}

2.5.5 算法原理3——贪心+二分【最优解】

本题最优解为算法>贪心算法。时间复杂度为O(N*logN)

贪心策略的核心，在于以下两点：

  1. 存什么：每个长度的递增序列中，存的是最后一个元素的最小值（假设x后面可以有一段递增序列，那么比x更小的数后面也一定可以有这个序列）【将数据存入数组hash中】
  2. 存哪里：存第一个大于等于nums[i]的位置(覆盖删除)

光靠文字也许晦涩难懂，下文已放图。 

如果我们仅仅按照以上策略来贪心的话，每个新元素查找插入位置的时间为O(N)，整体的时间复杂度也依然是O(N^2)，但是发现我们存放数据的数组hash满足递增的特性，故我们可以使用二分的方法寻找插入位置——优化为O(logN)，将整体的时间复杂度优化为：O(N*logN)

所以本题的解题原理为：贪心策略 + 二分查找 

2.5.6 算法代码3——贪心+二分【最优解】

java">class Solution {//贪心 + 二分查找public int lengthOfLIS(int[] nums) {int n = nums.length;List<Integer> hash = new ArrayList<>();for(int i = 0; i < n; i++) {int val = nums[i];int left = 0, right = hash.size() - 1;//hash为空//新元素比所有元素都大时，直接插入到最后if(hash.size() == 0 || val > hash.get(right)) {hash.add(val);continue;}//二分插入位置（hash为有序数组）while(left < right) {int mid = left + (right - left) / 2;if(hash.get(mid) < val) left = mid + 1;else right = mid; }hash.set(left, val);}return hash.size();}
}

END


http://www.ppmy.cn/ops/122017.html

相关文章

Vue2中的监听和计算属性的区别

Vue2中的监听和计算属性的区别

一、监听Watch 监听器&#xff08;Watchers&#xff09;是一种机制&#xff0c;用于在数据发生变化时执行特定的操作。监听器允许你监视 Vue 实例中的数据变化&#xff0c;并在数据变化时执行自定义的逻辑。 1、支持异步操作 2、接收两个参数&#xff0c;第一个是最新的值&…
阅读更多...
C语言基础之数组

C语言基础之数组

上一篇讲述了C语言函数的使用&#xff0c;本文讲述数组的相关概念&#xff0c;通过一维数组、二维数组、数组越界等详细讲解数组相关的具体内容&#xff0c;以辅助读者了解并掌握数组相关概念。 一维数组 一维数组的定义与创建 若无数组&#xff0c;我们要存储一堆类型相同的…
阅读更多...
分享我“Excel 表格”关键字的博客笔记（python脚本全程自动）

分享我“Excel 表格”关键字的博客笔记（python脚本全程自动）

Python脚本全程自动&#xff0c;全部Python内建工具脚本纯净。 (笔记模板由python脚本于2024年10月05日 19:51:06创建&#xff0c;本篇笔记适合喜欢Excel和Python的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&#xff1a;大…
阅读更多...
工厂模式与建造者模式的区别

工厂模式与建造者模式的区别

在软件设计中&#xff0c;工厂模式和建造者模式是两种常见的设计模式&#xff0c;它们都是用于创建对象&#xff0c;但是各自有不同的应用场景和目的。本文将通过餐馆点餐的例子&#xff0c;深入探讨这两种模式的区别。 工厂模式 工厂模式的核心思想是通过一个抽象工厂类来创…
阅读更多...
Vue-Lecture1-Notes

Vue-Lecture1-Notes

渐进式框架 Vue 被称为“渐进式框架”&#xff0c;是因为它允许开发者根据项目的需求逐步引入和使用其功能&#xff0c;而不需要一次性使用整个框架。简单来说&#xff0c;Vue 提供了从简单到复杂的功能层次&#xff0c;可以灵活选择使用。 按需使用&#xff1a;Vue 的核心功能…
阅读更多...
【MYSQL】mysql约束---自增长约束（auto_increment）

【MYSQL】mysql约束---自增长约束（auto_increment）

1、概念 在Mysql中&#xff0c;当主键为自增长后&#xff0c;这个主键的值就不再需要用户输入数据了&#xff0c;而由数据库系统根据定义自动赋值。每增加一条记录&#xff0c;主键会自动以相同的步长进行增长。 注意&#xff1a;自增长约束通常与主键放在一起使用。 通过给…
阅读更多...
SQL第11课——使用子查询

SQL第11课——使用子查询

11.1 子查询 查询&#xff08;query): 任何SQL语句都是查询&#xff0c;但此术语一般指select语句。 select语句是SQL的查询&#xff0c;迄今为止所有的select语句都是简单查询&#xff0c;即从单个数据库表中检索数据的单条语句。 SQL还允许创建子查询&#xff08;subquer…
阅读更多...
Spring的热部署工具和数据库密码加盐操作

Spring的热部署工具和数据库密码加盐操作

1.布置热部署 引言&#xff1a;在程序运行起来后&#xff0c;如果我们对代码进行了修改&#xff0c;需要重新测试修改后的程序&#xff0c;就得重新启动程序&#xff0c;这样很麻烦。于是引入热部署之后&#xff0c;我们就不需要重新启动程序&#xff0c;会自动更正。 1.配置po…
阅读更多...
最新文章

Copyright @ 2022~2023