贪心算法相关题目

1. 什么是贪心？

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。

2. 分发饼干

题目：

思路：
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

代码：

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

3. 摆动序列

题目：

思路：
本题要考虑三种情况：

情况一：上下坡中有平坡
情况二：数组首尾两端
情况三：单调坡中有平坡
记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)
代码：

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

4. 最大子数组和

题目：

思路：
采用贪心策略，如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”
代码：

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

5. 买卖股票的最佳时机 II

题目：

思路：
采用贪心策略，局部最优：收集每天的正利润，全局最优：求得最大利润。

代码：

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

6. 跳跃游戏

题目：

思路：
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
代码：

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

7. 跳跃游戏 II

题目：

思路：

理解本题的关键在于：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点，这个范围内最少步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。

代码：

class Solution:def jump(self, nums: List[int]) -> int:if len(nums) == 1:return 0result = 0max_cover = 0cur = 0while cur <= max_cover:for i in range(cur,max_cover + 1):max_cover = max(nums[i] + i,max_cover)if max_cover >= len(nums) - 1:result += 1return resultresult += 1return result

8.K 次取反后最大化的数组和

题目：

思路：
本题的解题步骤为：

第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K–
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和

代码：

class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums.sort(key=lambda x:abs(x),reverse=True)  # 按绝对值从大到小排序result = 0for i in range(len(nums)):if k > 0 and nums[i] < 0:nums[i] = -nums[i]k -= 1if k % 2 == 1:nums[-1] = -nums[-1]result = sum(nums)return result

9.加油站

题目：

思路：
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量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

10.分发糖果

题目：

思路：
这道题目一定是要确定一边之后，再确定另一边。分别从前往后和从后往前遍历，需要同时满足才行，有局部最优推出全局最优。

代码：

class Solution:def candy(self, ratings: List[int]) -> int:geting = [1] * len(ratings)result = 0for i in range(1,len(ratings)):  # 从左往右if ratings[i] > ratings[i - 1]:geting[i] = geting[i - 1] + 1for i in range(len(ratings)-2,-1,-1):   # 从右往左if ratings[i] > ratings[i + 1]:geting[i] = max(geting[i],geting[i + 1] + 1)for i in range(len(geting)):  result += geting[i]return result

11.柠檬水找零

题目：

思路：
只需要维护三种金额的数量，5，10和20。

有如下三种情况：

情况一：账单是5，直接收下。
情况二：账单是10，消耗一个5，增加一个10
情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

代码：

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

12.根据身高重建队列

题目：

思路：

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

知识点：

1. sort() 函数

sort() 函数用于对原列表进行排序，如果指定参数，则使用比较函数指定的比较函数。

list.sort( key=None, reverse=False)

• key – 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
• reverse – 排序规则，reverse = True 降序， reverse = False 升序（默认）。

1. people.sort(key=lambda x: (-x[0], x[1]))

这行代码是在Python中对一个列表（或其他可迭代对象）进行排序操作。让我们来解释一下：

people.sort: 这是对列表进行排序的方法调用。它会就地修改列表，而不是返回一个新的排序后的列表。

key=lambda x: (-x[0], x[1]): 这是一个关键字参数，用来指定排序时的关键函数。lambda x: (-x[0], x[1])是一个匿名函数，它接受一个参数x，表示列表中的每个元素，然后返回一个元组。

-x[0]: 这部分是元组的第一个元素，x[0]是列表中每个元素的第一个值。但是在这里，我们用负号来表示对该值取负。这意味着列表将会按照第一个值的逆序排列。

x[1]: 这部分是元组的第二个元素，x[1]是列表中每个元素的第二个值。它将会在第一个值相同的情况下进行正常的升序排序。

综合起来，这行代码的作用是先按列表中元素的第一个值进行降序排序，如果第一个值相同，则按照第二个值进行升序排序。

2. insert() 函数

insert() 函数用于将指定对象插入列表的指定位置。

list.insert(index, obj)

index – 对象obj需要插入的索引位置。
obj – 要插入列表中的对象。

代码：

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

13.用最少数量的箭引爆气球

题目：

思路：
先按数组的左边界进行排序，然后：

代码：

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

14. 无重叠区间

题目：

思路：
与上一题思路一致

代码：

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if len(intervals) == 0:return 0intervals.sort(key=lambda x:(x[0],x[1]))result = 0for i in range(1,len(intervals)):if intervals[i][0] < intervals[i - 1][1]:result += 1intervals[i][1] = min(intervals[i - 1][1],intervals[i][1])return result

15.划分字母区间

题目：

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

可以分为如下两步：

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

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

16.合并区间

题目：

思路：

代码：

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

17.单调递增的数字

题目：

思路：
利用贪心算法，从后往前遍历

代码：

class Solution:def monotoneIncreasingDigits(self, N: int) -> int:# 将整数转换为字符串strNum = str(N)# flag用来标记赋值9从哪里开始# 设置为字符串长度，为了防止第二个for循环在flag没有被赋值的情况下执行flag = len(strNum)# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:flag = i  # 更新flag的值，记录需要修改的位置# 将前一个字符减1，以保证递增性质strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]# 将flag位置及之后的字符都修改为9，以保证最大的递增数字for i in range(flag, len(strNum)):strNum = strNum[:i] + '9' + strNum[i + 1:]# 将最终的字符串转换回整数并返回return int(strNum)

18.监控二叉树

题目：

思路：
大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。
https://www.pr思路ogrammercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

代码：

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