即墨网站推广,网站页面下载,网站文章正文可以做内链吗,重庆网上中介服务超市文章目录 1. 什么是贪心#xff1f;2. 分发饼干3. 摆动序列4. 最大子数组和5. 买卖股票的最佳时机 II6. 跳跃游戏7. 跳跃游戏 II8.K 次取反后最大化的数组和9.加油站10.分发糖果11.柠檬水找零 1. 什么是贪心#xff1f;
贪心的本质是选择每一阶段的局部最优#xff0c;从而… 文章目录 1. 什么是贪心2. 分发饼干3. 摆动序列4. 最大子数组和5. 买卖股票的最佳时机 II6. 跳跃游戏7. 跳跃游戏 II8.K 次取反后最大化的数组和9.加油站10.分发糖果11.柠檬水找零 1. 什么是贪心
贪心的本质是选择每一阶段的局部最优从而达到全局最优。
例如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿
指定每次拿最大的最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
2. 分发饼干
题目 思路 大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。 代码
class Solution:def findContentChildren(self, g, s):g.sort() # 将孩子的贪心因子排序s.sort() # 将饼干的尺寸排序index len(s) - 1 # 饼干数组的下标从最后一个饼干开始result 0 # 满足孩子的数量for i in range(len(g)-1, -1, -1): # 遍历胃口从最后一个孩子开始if index 0 and s[index] g[i]: # 遍历饼干result 1index - 1return result3. 摆动序列
题目 思路 本题要考虑三种情况
情况一上下坡中有平坡 情况二数组首尾两端 情况三单调坡中有平坡 记录峰值的条件应该是 (preDiff 0 curDiff 0) || (preDiff 0 curDiff 0) 代码
class Solution:def wiggleMaxLength(self, nums):if len(nums) 1:return len(nums) # 如果数组长度为0或1则返回数组长度curDiff 0 # 当前一对元素的差值preDiff 0 # 前一对元素的差值result 1 # 记录峰值的个数初始为1默认最右边的元素被视为峰值for i in range(len(nums) - 1):curDiff nums[i 1] - nums[i] # 计算下一个元素与当前元素的差值# 如果遇到一个峰值if (preDiff 0 and curDiff 0) or (preDiff 0 and curDiff 0):result 1 # 峰值个数加1preDiff curDiff # 注意这里只在摆动变化的时候更新preDiffreturn result # 返回最长摆动子序列的长度4. 最大子数组和
题目 思路 采用贪心策略如果 -2 1 在一起计算起点的时候一定是从 1 开始计算因为负数只会拉低总和这就是贪心贪的地方
局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。
全局最优选取最大“连续和” 代码
class Solution:def maxSubArray(self, nums):result float(-inf) # 初始化结果为负无穷大count 0for i in range(len(nums)):count nums[i]if count result: # 取区间累计的最大值相当于不断确定最大子序终止位置result countif count 0: # 相当于重置最大子序起始位置因为遇到负数一定是拉低总和count 0return result5. 买卖股票的最佳时机 II
题目 思路 采用贪心策略局部最优收集每天的正利润全局最优求得最大利润。 代码
class Solution:def maxProfit(self, prices: List[int]) - int:result 0num 0for i in range(len(prices) - 1):num prices[i 1] - prices[i]if num 0:result numreturn result6. 跳跃游戏
题目 思路 贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。 代码
class Solution:def canJump(self, nums: List[int]) - bool:cover 0if len(nums) 1: return Truei 0# python不支持动态修改for循环中变量,使用while循环代替while i cover:cover max(i nums[i], cover)if cover len(nums) - 1: return Truei 1return False7. 跳跃游戏 II
题目 思路
理解本题的关键在于以最小的步数增加最大的覆盖范围直到覆盖范围覆盖了终点这个范围内最少步数一定可以跳到不用管具体是怎么跳的不纠结于一步究竟跳一个单位还是两个单位。
代码
class Solution:def jump(self, nums: List[int]) - int:if len(nums) 1:return 0result 0max_cover 0cur 0while cur max_cover:for i in range(cur,max_cover 1):max_cover max(nums[i] i,max_cover)if max_cover len(nums) - 1:result 1return resultresult 1return result8.K 次取反后最大化的数组和
题目 思路 本题的解题步骤为
第一步将数组按照绝对值大小从大到小排序注意要按照绝对值的大小 第二步从前向后遍历遇到负数将其变为正数同时K– 第三步如果K还大于0那么反复转变数值最小的元素将K用完 第四步求和
代码
class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) - int:nums.sort(keylambda x:abs(x),reverseTrue) # 按绝对值从大到小排序result 0for i in range(len(nums)):if k 0 and nums[i] 0:nums[i] -nums[i]k - 1if k % 2 1:nums[-1] -nums[-1]result sum(nums)return result9.加油站
题目 思路 首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSum。
代码
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int:curSum 0 # 当前累计的剩余油量totalSum 0 # 总剩余油量start 0 # 起始位置for i in range(len(gas)):curSum gas[i] - cost[i]totalSum gas[i] - cost[i]if curSum 0: # 当前累计剩余油量curSum小于0start i 1 # 起始位置更新为i1curSum 0 # curSum重新从0开始累计if totalSum 0:return -1 # 总剩余油量totalSum小于0说明无法环绕一圈return start10.分发糖果
题目 思路 这道题目一定是要确定一边之后再确定另一边。分别从前往后和从后往前遍历需要同时满足才行有局部最优推出全局最优。
代码
class Solution:def candy(self, ratings: List[int]) - int:geting [1] * len(ratings)result 0for i in range(1,len(ratings)): # 从左往右if ratings[i] ratings[i - 1]:geting[i] geting[i - 1] 1for i in range(len(ratings)-2,-1,-1): # 从右往左if ratings[i] ratings[i 1]:geting[i] max(geting[i],geting[i 1] 1)for i in range(len(geting)): result geting[i]return result11.柠檬水找零
题目 思路 只需要维护三种金额的数量510和20。
有如下三种情况
情况一账单是5直接收下。 情况二账单是10消耗一个5增加一个10 情况三账单是20优先消耗一个10和一个5如果不够再消耗三个5
局部最优遇到账单20优先消耗美元10完成本次找零。全局最优完成全部账单的找零。
代码
class Solution:def lemonadeChange(self, bills: List[int]) - bool:five 0ten 0 for bill in bills:# 情况一收到5美元if bill 5:five 1# 情况二收到10美元if bill 10:if five 0:return Falseten 1five - 1# 情况三收到20美元if bill 20:# 先尝试使用10美元和5美元找零if five 0 and ten 0:five - 1ten - 1#twenty 1# 如果无法使用10美元找零则尝试使用三张5美元找零elif five 3:five - 3else:return Falsereturn True
