贪心算法实战3

前言

今天继续带大家进行贪心算法的实战篇3，本章注意来解答一些运用贪心算法的比较难的问题，大家好好体会，怎么从构建局部最优到全局最优的。一文带大家弄懂。本文用于记录自己的学习过程，同时向大家进行分享相关的内容。本文内容参考于代码随想录同时包含了自己的许多学习思考过程，如果有错误的地方欢迎批评指正！

区间问题

跳跃游戏

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

**相关技巧：**其实跳跃游戏的解题思路就类似于一个搭桥的过程。如下所示，每一步都有个长度，我用着这个长度来搭桥，用来更新我能够最远到达的地方，如果能够到达终点，那么我们搭建的桥就肯定能够超过最大的下标。

这道题目关键点在于：不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。

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

跳跃游戏II

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

**相关技巧：**这题确实比刚才的跳跃游戏难了点，但其实本质上是一样的，这回题目说了肯定能够到达终点的。那我们考虑的就是怎么用最少的次数跳过去。

其实很简单，我们来看，2，3，1，1，4，从第一格开始我们能跳最远两步，然后我们跳的这两步之内，能够延伸我的桥，就是能跳的最远的，怎么让步数最少就是我们在我们能跳的格子内，哪一个能够让我们的桥延伸的更远，搭的更远就是我们需要的，最终得到的结果肯定就是最少的跳跃次数了。而且也很经典的贪心思想了。

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

用最少数量的箭引爆气球

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

**相关技巧：**如何用最少的弓箭呢？那不肯定就得是每次射掉重叠最多的气球，那最后用的肯定就是最少的弓箭了。

那重点来了，我们怎么去判定重叠的情况，去确定重叠的时候射哪个位置呢？

其实就是确定其最右边界，而且射爆气球后，我们也不需要从中删掉，只需要向下一个遍历即可。

所以理解了之后，再看这道题就很容易解出来了。看代码就能深刻的理解了。首先先进行排序，然后遍历，找最右边界的过程，当超过了就加一支箭。

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

无重叠区间

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

**相关技巧：**来看这道题，我们要找的无重叠区间，这么看好像是没有什么思路。但是我们想一下，我们去射气球的时候找的是什么，重叠区间，那我们将重叠区间找出来了，直接总区间减去重叠区间，剩下的就是我们需要去移除的区间了。

所以我们要做的与用最少数量的箭引爆气球是一样的，首先按照左边界升序排列，我们在找出重叠的区间，注意这里仅仅有一个细节不一样，射气球的时候$intervals[i][0]>intervals[i-1][1]$这里是不带等号的，因为那时候题目说是算重叠的，但是本题就得带等号了，因为在这题里面这就不算重叠了。

最后我们找出所有的重叠区间，让总区间减去重叠的区间就是我们需要去移除的区间了。

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if not intervals:return 0intervals.sort(key=lambda x: x[0])  # 按照左边界升序排序result = 1  # 不重叠区间数量，初始化为1，因为至少有一个不重叠的区间for i in range(1, len(intervals)):if intervals[i][0] >= intervals[i - 1][1]:  # 没有重叠result += 1else:  # 重叠情况intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  # 更新重叠区间的右边界return len(intervals) - result

划分字母区间

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

**相关技巧：**在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

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

一张图片你就能很清晰的懂得了，然后写出代码即可

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

合并区间

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

**相关技巧：**本题的本质其实还是判断重叠区间问题。其实还是一个套路，只不过区别就是判断区间重叠后的逻辑，本题是判断区间重贴后要进行区间合并。

所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）

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

最大子序和

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

**相关技巧：**首先我们来看题目，我们需要求最大和的连续子数组，那么怎么去得到最大呢？很简单，我们需要保证当前的连续和是大于零的，这样我们加入下一个数的时候就不会拖累下一个数。这也就是贪心思想的体现。

比如说当前第一个-2，要加下一个1了，我们需要去加这个-2吗？之前的连续和都变成负数了，对于我们后面的找最大连续和来说一定会是个累赘。所以我们下一个就是1开始，然后加-3变成-2。又变成负数了，再从下一个重新开始。4加-1是3，虽然减少了，但是其还是正的，会对下一个数的累加有帮助，**当然了，我们这里会有个记录最大的，如果后面加起来成负数了，就会记录上4是最大的。**所以继续加2，变成5，再加1变成6，**这里会记录上，更新之后最大的是6的。**然后在加-5和4，变成5，虽然也是正的，但是之前记录了最大的就是6，所以我们的最大连续子数组和是6。

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

加油站

134. 加油站 - 力扣（LeetCode）

**相关技巧：**首先来看题目，我们进行分析：如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从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  # 起始位置更新为i+1curSum = 0  # curSum重新从0开始累计if totalSum < 0:return -1  # 总剩余油量totalSum小于0，说明无法环绕一圈return start

监控二叉树

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

**相关技巧：**我们从题目中其实能看出来，摄像头是不会放在叶子节点的，因为摄像头能够覆盖上中下三层，所以放在叶子节点或者头节点就会特别浪费，其次我们遍历从叶子节点开始往上遍历，为什么不从头节点呢？因为哪怕头节点放一个摄像头就只浪费一个，但是叶子节点的话那就是指数级别的了。所以我们的遍历顺序选择后序遍历。

我们用三个数字来表示不同的状态，这样方便我们判定是否放摄像头：

• 0：该节点无覆盖
• 1：本节点有摄像头
• 2：本节点有覆盖

主要有如下四类情况：

• 情况1：左右节点都有覆盖

• 情况2：左右节点至少有一个无覆盖的情况

• 情况3：左右节点至少有一个有摄像头

• 情况4：头结点没有覆盖

所以我们需要加摄像头的情况只有情况1和情况4。

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 左节点覆盖，右节点无覆盖if left == 0 or right == 0:result[0] += 1return 1# 情况3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头if left == 1 or right == 1:return 2