天津建站方案,合肥网站优化搜索,怎么申请网站,app制作平台灼灼琉璃夏漫画青铜挑战-贪心其实很简单
1. 难以解释的贪心算法
贪心学习法则#xff1a;直接做题#xff0c;不考虑贪不贪心
贪心(贪婪)算法 是指在问题尽心求解时#xff0c;在每一步选择中都采取最好或者最优#xff08;最有利#xff09;的选择#xff0c;从而希望能够导致结果最…青铜挑战-贪心其实很简单
1. 难以解释的贪心算法
贪心学习法则直接做题不考虑贪不贪心
贪心(贪婪)算法 是指在问题尽心求解时在每一步选择中都采取最好或者最优最有利的选择从而希望能够导致结果最好或者最优的算法
贪心算法所得到的结果不一定是最优的结果但是都是相对近似最优解的结果
怎么知道什么时候改用贪心呢 要求要解决的问题具有“最优子结构”
贪心怎么学 将常见的贪心题都找出来看看大致是什么样子的学一学就行了
贪心常见的应用场景
排序问题选择排序、拓扑排序优先队列堆排序赫夫曼压缩编码图里的 Prim、Fruska和Dijkstra算法硬币找零问题分数背包问题并查集的按大小或者高度合并问题或者排名任务调度部分场景一些复杂的近似算法
2. 贪心问题举例
2.1 分发饼干
LeetCode 455 https://leetcode.cn/problems/assign-cookies/
思路分析
既要满足小孩的胃口也不要造成饼干的浪费 大饼干既可以满足胃口大的孩子也可以满足胃口小的孩子就应该优先满足胃口大的
局部最优大饼干喂给胃口大的充分利用饼干尺寸喂饱一个 全局最优喂饱尽可能多的孩子
贪心策略考虑胃口大饼干先喂饱大胃口最后看能满足几个孩子的需要
先将饼干数组和小孩数组排序然后从后向前比那里小孩数组用大饼干优先满足胃口大的并统计满足孩子的数量 代码实现
class Solution:def findContentChildren(self, g: List[int], s: List[int]) - int:g.sort(reverseTrue)s.sort(reverseTrue)s_len len(s)s_index 0count 0for i in g:if s_index s_len and i s[s_index]:s_index 1count 1return count2.2 柠檬水找零
LeetCode860 https://leetcode.cn/problems/lemonade-change/
思路分析
分析下主要有三种情况
给的是5直接收下给的是10给出1个5此时必须要有1个5才行给的是20优先消耗1个10再给1个5。如果没有10给出3个5
局部最优遇到账单20优先消耗10完成本次找零。10只能给20找零5更万能
代码实现
class Solution:def lemonadeChange(self, bills: List[int]) - bool:count_5 0count_10 0for money in bills:if money 5:count_5 1elif money 10:count_5 - 1count_10 1elif money 20:if count_10 0:count_10 - 1count_5 - 1else:count_5 - 3if count_5 0 or count_10 0:return Falsereturn True
2.3 分发糖果
LeetCode 135 https://leetcode.cn/problems/candy/
思路分析
每个孩子至少一个糖果 相邻孩子评分更高的获得更多的糖果
第一轮从左到右 只要右边的比左边的大就一直加1如果右边比左边小就设置为1 第二轮从右到左 如果左边的比右边的大在{i1}的基础上先加1再赋值给{i} 每个位置i从left[i]和right[i]中选最大就行了
第一轮
下标 0 1 2 3 4 5 6
得分 1 2 2 5 4 3 2
糖果 1 2 1 2 1 1 1第二轮
下标 0 1 2 3 4 5 6
得分 1 2 2 5 4 3 2
糖果 1 2 1 4 3 2 1选取最大
下标 0 1 2 3 4 5 6
得分 1 2 2 5 4 3 2
糖果 1 2 1 4 3 2 1第一轮
下标 0 1 2 3 4
得分 1 3 4 5 2
糖果 1 2 3 4 1第二轮
下标 0 1 2 3 4
得分 1 3 4 5 2
糖果 1 2 3 2 1选取最大
下标 0 1 2 3 4
得分 1 3 4 5 2
糖果 1 2 3 4 1代码实现
class Solution:def candy(self, ratings: List[int]) - int:n len(ratings)candy_list [0] * ncandy_list[0] 1 for i in range(1, n):if ratings[i] ratings[i-1]:candy_list[i] candy_list[i-1] 1else:candy_list[i] 1for i in range(n-2, -1, -1):if ratings[i] ratings[i1]:candy_list[i] max(candy_list[i1] 1, candy_list[i])return sum(candy_list)
