【LeetCode 刷题】贪心算法(2)-进阶
此博客为《代码随想录》贪心算法章节的学习笔记，主要内容为贪心算法进阶的相关题目解析。
文章目录
- 135. 分发糖果
- 406. 根据身高重建队列
- 134. 加油站
- 968. 监控二叉树
135. 分发糖果
题目链接
class Solution:def candy(self, ratings: List[int]) -> int:n = len(ratings)left = [1] * nfor i in range(1, n):if ratings[i] > ratings[i-1]:left[i] = left[i-1] + 1right = [1] * nres = left[n-1]for i in range(n - 2, -1, -1):if ratings[i] > ratings[i+1]:right[i] = right[i+1] + 1res += max(left[i], right[i])return res
- 将同时考虑两侧的元素分解为左右两个规则：
- 左规则：只考虑当前元素和其左侧的元素，使其满足题目要求
- 右规则：只考虑当前元素和其右侧的元素，使其满足题目要求
- 先从左至右遍历，获得满足左规则的序列；再从右至左遍历，获得满足右规则的序列；最后每个位置取两序列的最大值，累加即为答案
406. 根据身高重建队列
题目链接
class Solution:def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:people.sort(key=lambda x: (-x[0], x[1]))res = []for p in people:if p[1] < len(res):res.insert(p[1], p)else:res.append(p)return res
- 先按照身高降序排序，然后按照排位升序排序，按照排序后的数组顺序处理，根据当前元素的排位在结果序列中动态插队（因为按身高降序排列后，比当前元素高的元素都已经被处理过且放入
res中，而后续未处理的元素又比当前元素矮，不影响结果）
134. 加油站
题目链接
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:cur_gas, sum_gas = 0, 0res = 0for i in range(len(gas)):cur_gas += gas[i] - cost[i]sum_gas += gas[i] - cost[i]if cur_gas < 0:res = i + 1cur_gas = 0return res if sum_gas >= 0 else -1
- 从 0 号站点开始累加，一旦
cur_sum小于零，则表示之前所有的站点都不可能作为起点，选择下一个位置作为新的起点，cur_sum重新开始累加 sum_gas在遍历过程中累计全程所有的油量，如果sum_gas < 0则表示不可能开完一圈，返回 -1。
968. 监控二叉树
题目链接
class Solution:def minCameraCover(self, root: Optional[TreeNode]) -> int:# 0 无覆盖 1 有覆盖 2 有摄像头def traversal(node: Optional[TreeNode]) -> int:if not node:return 1left = traversal(node.left)right = traversal(node.right)if left == 1 and right == 1:return 0if left == 0 or right == 0:nonlocal resres += 1return 2if left == 2 or right == 2:return 1res = 0val = traversal(root)if val == 0: res += 1 # 根结点无覆盖return res
- 贪心准则：尽可能不要让覆盖的范围重合
- 设置三个节点的状态：0 无覆盖；1 有覆盖；2 有摄像头
- 两个子节点有任何一个为无覆盖的状态，则当前节点需要放置摄像头
- 两个子节点有任何一个有摄像头，则当前节点为有覆盖状态
- 两个子节点都有覆盖（说明是孙子节点的摄像头），则当前节点为无覆盖
- 根据贪心准则，叶子结点是不需要放置摄像头的，因此将空节点返回的状态值设置为 1 有覆盖，这样叶子结点的状态值则为 0 无覆盖，满足算法要求
- 最后判断根节点的状态，如果为无覆盖，则需要额外再放一个摄像头