力扣整理版九：贪心算法

局部最优  全局最优  局部最优可以推出全局最优  并且想不出反例

-----------------------------

(1) 455 分发饼干

(2) 1005 k次取反后最大化的数组和

(3) 860 柠檬水找零

(4) 376 摆动序列

(5) 738 单调递增的数字

(6) 122 买卖股票的最佳时机2

(7) 135 分发糖果

(8) 406 根据身高重建队列

(9) 55 跳跃游戏

(10) 45 跳跃游戏2

(11) 452 用最少的箭引爆气球

(12) 435 无重叠区间

(13) 763 划分字母区间

(14) 56 合并区间

(15) 53 最大子序和

(16) 134 加油站

(17) 968 监控二叉树

-----------------------------

一、简单题目

1、455 分发饼干

455. 分发饼干 - 力扣（LeetCode）

题目描述：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值  g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

--------------- python ---------------

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 result

2、1005 k次取反后最大化的数组和 

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

题目描述：给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）以这种方式修改数组后，返回数组可能的最大和。

class Solution:def largestSumAfterKNegations(self, A: List[int], K: int) -> int:A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组Afor i in range(len(A)):  # 第二步：执行K次取反操作if A[i] < 0 and K > 0:A[i] *= -1K -= 1if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反A[-1] *= -1result = sum(A)  # 第四步：计算数组A的元素和return result

3、860 柠檬水找零 

860. 柠檬水找零 - 力扣（LeetCode）

题目描述：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

--------------- python ---------------

class Solution:def lemonadeChange(self, bills: List[int]) -> bool:five = 0ten = 0twenty = 0for 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 -= 3#twenty += 1else:return Falsereturn True

二、中等题目-序列问题

1、376 摆动序列

376. 摆动序列 - 力扣（LeetCode）

题目描述：给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

--------------- python ---------------

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  # 返回最长摆动子序列的长度

2、738 单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

题目描述：给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

Tips：两位数的情况--十位数减一，个位数变为9。需要从后向前，332，前向后是329，但是又不满足递增了。从后向前，有递减，后面全部为9，前一位减1（保证比原数小）。

--------------- python ---------------

class Solution:def monotoneIncreasingDigits(self, N: int) -> int:strNum = str(N)        for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:# 将前一个字符减1，以保证递增性质# 使用字符串切片操作将修改后的前面部分与后面部分进行拼接strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)       return int(strNum)

附一种错误的，写的时候理所当然感觉只要有递减就最高位-1，后面全部为9，这种情况120输出99，但是实际上是119。需要两位数两位数比较。 

class Solution:def monotoneIncreasingDigits(self, n: int) -> int:strnum=str(n)for i in range(len(strnum)-1):if strnum[i]>strnum[i+1]:return int(str(int(strnum[0])-1)+'9'*(len(strnum)-1))return n

三、中等题目-贪心解决股票

1、122 买卖股票的最佳时机2

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

题目描述：给定一个数组，它的第  i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

Tips：只收集每天的正利润。

--------------- python ---------------

class Solution:def maxProfit(self, prices: List[int]) -> int:result = 0for i in range(1, len(prices)):result += max(prices[i] - prices[i - 1], 0)return result

四、中等题目-两个维度权衡

1、135 分发糖果

135. 分发糖果 - 力扣（LeetCode）

题目描述：老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

Tips：考虑两边的情况一定要分开遍历。

--------------- python ---------------

class Solution:def candy(self, ratings: List[int]) -> int:candyVec = [1] * len(ratings)# 从前向后遍历，处理右侧比左侧评分高的情况for i in range(1, len(ratings)):if ratings[i] > ratings[i - 1]:candyVec[i] = candyVec[i - 1] + 1# 从后向前遍历，处理左侧比右侧评分高的情况for i in range(len(ratings) - 2, -1, -1):if ratings[i] > ratings[i + 1]:candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1)# 统计结果result = sum(candyVec)return result

2、406 根据身高重建队列 

406. 根据身高重建队列 - 力扣（LeetCode）

题目描述：假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:# 先按照h维度的身高顺序从高到低排序。确定第一个维度# lambda返回的是一个元组：当-x[0](维度h）相同时，再根据x[1]（维度k）从小到大排序people.sort(key=lambda x: (-x[0], x[1]))que = []# 根据每个元素的第二个维度k，贪心算法，进行插入# people已经排序过了：同一高度时k值小的排前面。for p in people:que.insert(p[1], p)return que

五、有点难度-区间问题

1、55 跳跃游戏

55. 跳跃游戏 - 力扣（LeetCode）

题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

Tips：关注的是跳跃覆盖范围。

--------------- python ---------------

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 False

2、45 跳跃游戏2 

45. 跳跃游戏 II - 力扣（LeetCode）

题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

Tips：只要i遇到当前最大范围，加+1。

--------------- python ---------------

class Solution:def jump(self, nums):cur_distance = 0  # 当前覆盖的最远距离下标ans = 0  # 记录走的最大步数next_distance = 0  # 下一步覆盖的最远距离下标for i in range(len(nums) - 1):  # 注意这里是小于len(nums) - 1，这是关键所在next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖的最远距离下标if i == cur_distance:  # 遇到当前覆盖的最远距离下标cur_distance = next_distance  # 更新当前覆盖的最远距离下标ans += 1return ans

3、452 用最少数量的箭引爆气球 

452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

题目描述：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

--------------- python ---------------

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points) == 0: return 0points.sort(key=lambda x: x[0])result = 1for i in range(1, len(points)):if points[i][0] > points[i - 1][1]: # 气球i和气球i-1不挨着，注意这里不是>=result += 1     else:points[i][1] = min(points[i - 1][1], points[i][1]) # 更新重叠气球最小右边界return result

4、435 无重叠区间 

435. 无重叠区间 - 力扣（LeetCode）

题目描述：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

--------------- python ---------------

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if not intervals:return 0intervals.sort(key=lambda x: x[0])  # 按照左边界升序排序count = 0  # 记录重叠区间数量for i in range(1, len(intervals)):if intervals[i][0] < intervals[i - 1][1]:  # 存在重叠区间intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  # 更新重叠区间的右边界count += 1return count

5、763 划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

题目描述：字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

Tips：这道题不是很像贪心，没有局部最优推出全局最优的过程。(用最远距离模拟圈字符）

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

--------------- python ---------------

class Solution:def partitionLabels(self, s: str) -> List[int]:last_occurrence = {}  # 存储每个字符最后出现的位置for i, ch in enumerate(s):last_occurrence[ch] = iresult = []start = 0end = 0for i, ch in enumerate(s):end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间result.append(end - start + 1)start = i + 1return result

6、56 合并区间 

56. 合并区间 - 力扣（LeetCode）

题目描述：给出一个区间的集合，请合并所有重叠的区间。

--------------- python ---------------

class Solution:def merge(self, intervals):result = []if len(intervals) == 0:return result  # 区间集合为空直接返回intervals.sort(key=lambda x: x[0])  # 按照区间的左边界进行排序result.append(intervals[0])  # 第一个区间可以直接放入结果集中for i in range(1, len(intervals)):if result[-1][1] >= intervals[i][0]:  # 发现重叠区间# 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的result[-1][1] = max(result[-1][1], intervals[i][1])else:result.append(intervals[i])  # 区间不重叠return result

六、有点难度-其他

1、53 最大子序和

53. 最大子数组和 - 力扣（LeetCode）

题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

--------------- python ---------------

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 result

2、134 加油站

134. 加油站 - 力扣（LeetCode）

题目描述：在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

Tips：如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

--------------- python ---------------

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  # 起始位置更新为i+1curSum = 0  # curSum重新从0开始累计if totalSum < 0:return -1  # 总剩余油量totalSum小于0，说明无法环绕一圈return start

3、968 监控二叉树

968. 监控二叉树 - 力扣（LeetCode）

题目描述：给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

Tips：局部最优--叶子节点的父节点有摄像头；整体最优--全部摄像头数量最少。

--------------- python ---------------

class Solution:# Greedy Algo:# 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优# 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖def minCameraCover(self, root: TreeNode) -> int:# 定义递归函数result = [0]  # 用于记录摄像头的安装数量if self.traversal(root, result) == 0:result[0] += 1return result[0]def traversal(self, cur: TreeNode, result: List[int]) -> int:if not cur:return 2left = self.traversal(cur.left, result)right = self.traversal(cur.right, result)# 情况1: 左右节点都有覆盖if left == 2 and right == 2:return 0# 情况2:# left == 0 && right == 0 左右节点无覆盖# left == 1 && right == 0 左节点有摄像头，右节点无覆盖# left == 0 && right == 1 左节点无覆盖，右节点有摄像头# left == 0 && right == 2 左节点无覆盖，右节点覆盖# left == 2 && right == 0 左节点覆盖，右节点无覆盖elif left == 0 or right == 0:result[0] += 1return 1# 情况3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头else:return 2

附一个报错代码：（直接使用result作为一个值）

class Solution:def minCameraCover(self, root: Optional[TreeNode]) -> int:result=0if traversal(root)==0:result+=1def traversal(cur):#nonlocal result  需要nonlocal 修饰if not cur:return 2left=traversal(cur.left)right=traversal(cur.right)if left==2 and right==2:return 0elif left==0 or right==0:result+=1return 1else:return 2return result-----------------
1、这样子函数定义需要在函数调用前
2、在traversal函数内，你尝试修改result（result+=1）.
但是result在traversal函数的作用域外部定义.
因此在traversal函数内部直接修改它会导致错误。

再附一个错误：

class Solution:def minCameraCover(self, root: Optional[TreeNode]) -> int:result=0def traversal(cur,result):if not cur:return 2left=traversal(cur.left,result)right=traversal(cur.right,result)if left==2 and right==2:return 0elif left==0 or right==0:result+=1return 1else:return 2if traversal(root,result)==0:result+=1return result------------------
将result作为参数传递给traversal函数。
在递归过程中，即使修改了result，这个修改不会反映到外部作用域中。
最后输出就是0。