贪心算法实战3

目录

• 前言
  
• 区间问题
  
  
  
  • 跳跃游戏
    
  • 跳跃游戏II
    
  • 用最少数量的箭引爆气球
    
  • 无重叠区间
    
  • 划分字母区间
    
  • 合并区间
    
  
  
• 最大子序和
  
• 加油站
  
• 监控二叉树
  

前言

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

区间问题

跳跃游戏

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

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

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

1. class Solution:
2.     def canJump(self, nums: List[int]) -> bool:
3.         cover = 0
4.         if len(nums) == 1: return True
5.         i = 0
6.         # python不支持动态修改for循环中变量,使用while循环代替
7.         while i <= cover:
8.             cover = max(i + nums[i], cover)
9.             if cover >= len(nums) - 1: return True
10.             i += 1
11.         return False

复制代码

跳跃游戏II

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

相关技巧：这题确实比刚才的跳跃游戏难了点，但其实本质上是一样的，这回题目说了肯定能够到达终点的。那我们考虑的就是怎么用最少的次数跳过去。
其实很简单，我们来看，2，3，1，1，4，从第一格开始我们能跳最远两步，然后我们跳的这两步之内，能够延伸我的桥，就是能跳的最远的，怎么让步数最少就是我们在我们能跳的格子内，哪一个能够让我们的桥延伸的更远，搭的更远就是我们需要的，最终得到的结果肯定就是最少的跳跃次数了。而且也很经典的贪心思想了。

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

复制代码

用最少数量的箭引爆气球

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

相关技巧：如何用最少的弓箭呢？那不肯定就得是每次射掉重叠最多的气球，那最后用的肯定就是最少的弓箭了。
那重点来了，我们怎么去判定重叠的情况，去确定重叠的时候射哪个位置呢？

其实就是确定其最右边界，而且射爆气球后，我们也不需要从中删掉，只需要向下一个遍历即可。
所以理解了之后，再看这道题就很容易解出来了。看代码就能深刻的理解了。首先先进行排序，然后遍历，找最右边界的过程，当超过了就加一支箭。

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

复制代码

无重叠区间

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

相关技巧：来看这道题，我们要找的无重叠区间，这么看好像是没有什么思路。但是我们想一下，我们去射气球的时候找的是什么，重叠区间，那我们将重叠区间找出来了，直接总区间减去重叠区间，剩下的就是我们需要去移除的区间了。
所以我们要做的与用最少数量的箭引爆气球是一样的，首先按照左边界升序排列，我们在找出重叠的区间，注意这里仅仅有一个细节不一样，射气球的时候$intervals[0] > intervals[i - 1][1]$这里是不带等号的，因为那时候题目说是算重叠的，但是本题就得带等号了，因为在这题里面这就不算重叠了。
最后我们找出所有的重叠区间，让总区间减去重叠的区间就是我们需要去移除的区间了。

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

复制代码

划分字母区间

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

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

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

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

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

复制代码

合并区间

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

相关技巧：本题的本质其实还是判断重叠区间问题。其实还是一个套路，只不过区别就是判断区间重叠后的逻辑，本题是判断区间重贴后要进行区间合并。
所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

按照左边界从小到大排序之后，如果 intervals[0]  全局最优        # 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head        # 0: 该节点未覆盖        # 1: 该节点有摄像头        # 2: 该节点有覆盖    def minCameraCover(self, root: TreeNode) -> int:        # 定义递归函数        result = [0]  # 用于记录摄像头的安装数量        if self.traversal(root, result) == 0:            result[0] += 1        return result[0]            def traversal(self, cur: TreeNode, result: List[int]) -> int:        if not cur:            return 2        left = 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] += 1            return 1        # 情况3:        # left == 1 && right == 2 左节点有摄像头，右节点有覆盖        # left == 2 && right == 1 左节点有覆盖，右节点有摄像头        # left == 1 && right == 1 左右节点都有摄像头        if left == 1 or right == 1:            return 2[/code]
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！