leetcode—贪心算法总结_leetcode 贪心算法
lc455.分发饼干
都排序，小饼干给小胃口，如果不够喂，考虑下一个饼干
class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() g_cur = 0 s_cur = 0 while g_cur < len(g) and s_cur = g[g_cur]: s_cur += 1 g_cur += 1 else: s_cur += 1 return g_curlc376 摆动序列
up记录当前最长“最后一个差值为正”的子序列长度
down记录当前最长“最后一个差值为负”的子序列长度
每次都根据当前的差值做出更新
1：单调时，会一直更新值，但并不改变up与down的实际值（因为单调时不计数）
2：平台时，不更新
3：直到遇到“拐点时”，才会实际更新up和down
贪心思想：每次遇到差值，都认为这是一个拐点，进行更新，但是否实际更新了，要看是否是真的拐点，但我们只考虑目前这个差值。
class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: if len(nums) == 1: return 1 up = 1 down = 1 for i in range(1, len(nums)): if (nums[i] - nums[i-1]) > 0: up = down + 1 elif (nums[i] - nums[i-1]) < 0: down = up + 1 return max(up, down) lc53 最大的子数组和
res进行“打擂台”记录最大值
如果此时的连续和为负数，那这个连续和只会让后面的子数组和变得更小，不如抛弃，所以此时重新更新连续和为0，下一个num开始累计
class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: if len(nums) == 1: return 1 up = 1 down = 1 for i in range(1, len(nums)): if (nums[i] - nums[i-1]) > 0: up = down + 1 elif (nums[i] - nums[i-1]) < 0: down = up + 1 return max(up, down) lc122 买卖股票的最佳时机II
我只买赚钱的股票，加起来就是最大利润
class Solution: def maxProfit(self, prices: List[int]) -> int: pre = prices[0] res = 0 for price in prices: profit = price - pre if profit > 0: res += profit pre = price return reslc55 跳跃游戏
贪心思想，每次尽可能往前覆盖“可到达的范围”，本文为cover，当cover覆盖了终点时，一定可到达。
class Solution: def canJump(self, nums: List[int]) -> bool: if len(nums) == 1: return True cover = 0 i = 0 while i = len(nums) - 1: return True i += 1 return False lc45 跳跃游戏II
每次尽可能扩大cover（选择能够最大化cover的跳跃）
每次进行扩大cover时，就将步数+1
class Solution: def jump(self, nums: List[int]) -> int: res = 0 cur_cover = 0 next_cover = 0 i = 0 while i = len(nums) - 1: break else: res += 1 cur_cover = next_cover i += 1 return reslc1005 K次取反后最大化的数组和
按绝对值排序
最后结束for循环有三种情况：
1、k不够用（即k<负数个数），此时直接返回
2、k够用：此时数组已经全正
（1）k为偶数，直接返回
（2）k为奇数，对最小的非负数取反
class Solution: def largestSumAfterKNegations(self, nums: List[int], k: int) -> int: nums.sort(key=lambda x: abs(x), reverse=True) for i in range(len(nums)): if k > 0 and nums[i] < 0: nums[i] *= -1 k -= 1 if k % 2 == 1: nums[-1] *= -1 return sum(nums)lc134 加油站
这题的贪心思想有意思了
用delta来考虑，gas[i] - cost[i]，即经过此加油站所补充\\消耗的油量
我不妨用delta数组来存储这n个差值
首先我假设起点为0，然后去按顺序累加delta数组，当区间为【0，i】时，一旦发现累加和为负了，则更新起点为i+1，然后以i+1为起点，重新向后累加
以上过程，事实上是一种贪心构造 + 局部失败剪枝。
代码随想录的一句话：当【i，j】区间和为负时，【i，j】内不可能有可以作为起点的存在。
这其实是不严谨的
如果我们试图用反证法去证明，只会发现：
假设i+k存在于【i，j】之内，且作为起点，则【i+k，j】区间和为正，而因为【i，j】为负，则【i，i+k】为负，则i+k天然为一个起点。这分明就是可以存在一个起点的
因此这无法严格用反证法证明，这个说法本身不严谨
我们应该这样说：
我们在【i，j】失败的时候，直接从j+1作为起点再次开始尝试时，【i，j】内可以作为起点的地方已经被我们都尝试过了，这是一种剪枝手段，或者说，如果【i，j】内存在可以作为起点的地方如（i+k），我们现在应该正在尝试这个i+k，而不是i
也就是说，我们是在进行顺序尝试起点，进行了剪枝~
其次，只要满足sum（delta） >= 0（即总油量大于等于总消耗量），就一定存在一个合理起点可以走完一圈，为什么？
class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: total_sum = 0 for i in range(len(gas)): total_sum += (gas[i] - cost[i]) if total_sum < 0: return -1 i = 0 start = 0 cur_sum = 0 for i in range(len(gas)): #局部最优 cur_sum += (gas[i] - cost[i]) if cur_sum = 0 return startlc135 分发糖果
class Solution: def candy(self, ratings: List[int]) -> int: n = len(ratings) candy = [1] * n for i in range(1, n): if ratings[i] > ratings[i-1]: candy[i] = candy[i-1] + 1 for i in range(n-2, -1, -1): if ratings[i] > ratings[i+1]: candy[i] = max(candy[i], candy[i+1]+1) return sum(candy) lc860 柠檬水找零
遇到20，优先用10+5找零
class Solution: def lemonadeChange(self, bills: List[int]) -> bool: money_list = [0] * 2 if bills[0] != 5: return False for bill in bills: if bill == 5: money_list[0] += 1 elif bill == 10: if money_list[0] == 0: return False else: money_list[0] -= 1 money_list[1] += 1 else: if money_list[0] == 0: return False elif money_list[0] >= 1 and money_list[1] >= 1: money_list[0] -= 1 money_list[1] -= 1 continue elif money_list[0] >= 3: money_list[0] -= 3 continue return False return Truelc406 根据身高重建队列
两个维度，先搞定一个维度，再搞定第二个维度（确保第二个维度调整时，不影响第一个维度）
class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: queue = [] people.sort(key = lambda x: (-x[0], x[1])) for p in people: queue.insert(p[1], p) return queuelc452 用最少数量的箭射爆气球
按起点升序排
注意边界更新
class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: res = 1 points.sort(key = lambda x: x[0]) end = points[0][1] for i in range(1,len(points)): if points[i][0] <= end: end = min(end, points[i][1]) else: res += 1 end = points[i][1] return reslc435 无重叠区间
换句话讲，尽可能保留多的组数（组内两两重叠（一箭射爆），最后组内只留一个区间（且是end最小的区间，但这不重要，这题无需考虑这么细了）
最后 res = 总区间数 - 组数
所以和射箭是基本一直的，就是把箭数求出来
class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: group = 1 intervals.sort(key = lambda x: x[0]) end = intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] < end: end = min(end, intervals[i][1]) else: group += 1 end = intervals[i][1] return len(intervals) - grouplc763 划分字母区间
先得到每个字母最晚出现位置，再不断更新边界end，当到达边界end时，代表之前的字母已经出现完毕，后续不再出现，可划分出一个区间。
class Solution: def partitionLabels(self, s: str) -> List[int]: hash_table = [0] * 26 for i in range(len(s)): hash_table[ord(s[i]) - ord(\'a\')] = i pre_end = 0 end = 0 res = [] for i in range(len(s)): end = max(end, hash_table[ord(s[i]) - ord(\'a\')]) if i == end: res.append(end - pre_end + 1) pre_end = end + 1 return reslc56 合并区间
注意对end的更新，这里取的是max，而非min，意图为合并区间
class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key = lambda x: x[0]) res = [] min_left = intervals[0][0] end = intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] <= end: end = max(end, intervals[i][1]) else: res.append([min_left, end]) min_left = intervals[i][0] end = intervals[i][1] res.append([min_left, end]) return reslc738 单调递增的数字
从后往前遍历，这样可以利用到已修改的结果
遇到不符合的情况，就将当前及之后全部变为9，前一位-1。
class Solution: def monotoneIncreasingDigits(self, n: int) -> int: n = list(map(int, str(n))) flag = len(n) for i in range(len(n)-1, 0, -1): if n[i-1] > n[i]: flag = i n[i-1] -= 1 for i in range(flag, len(n)): n[i] = 9 return int(\"\".join(map(str, n)))lc968 监控二叉树
1、尽量在叶子节点的父节点放摄像头，放在叶子节点的话就浪费了，所以从下往上放
2、根据1的原则，采取后序遍历，根据左右孩子的状态来决定父节点的操作
3、
状态1：有覆盖
状态2：无覆盖
状态3：摄像头
4、特殊情况，根节点是没有父节点的，所以遍历完之后根节点可能是无覆盖的状态，此时单独处理
class Solution: def minCameraCover(self, root: Optional[TreeNode]) -> int: self.res = 0 # 1有覆盖 # 2无覆盖 # 3摄像头 def post_traversal(node): if not node: return 1 left_res = post_traversal(node.left) right_res = post_traversal(node.right) if left_res == 1 and right_res == 1: return 2 elif left_res == 2 or right_res == 2: self.res += 1 return 3 elif left_res == 3 or right_res == 3: return 1 if post_traversal(root) == 2: self.res += 1 return self.res
