文章目录
- 1. 什么是贪心？
- 2. 分发饼干
- 3. 摆动序列
- 4. 最大子数组和
- 5. 买卖股票的最佳时机 II
- 6. 跳跃游戏
- 7. 跳跃游戏 II
- 8.K 次取反后最大化的数组和
- 9.加油站
- 10.分发糖果
- 11.柠檬水找零
- 12.根据身高重建队列
- 13.用最少数量的箭引爆气球
- 14. 无重叠区间
- 15.划分字母区间
- 16.合并区间
- 17.单调递增的数字
- 18.监控二叉树
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 += 1
index -= 1
return 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 # 峰值个数加1
preDiff = curDiff # 注意这里，只在摆动变化的时候更新preDiff
return result # 返回最长摆动子序列的长度
4. 最大子数组和
题目：
思路：
采用贪心策略，如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
代码：
class Solution:
def maxSubArray(self, nums):
result = float('-inf') # 初始化结果为负无穷大
count = 0
for i in range(len(nums)):
count += nums[i]
if count > result: # 取区间累计的最大值（相当于不断确定最大子序终止位置）
result = count
if count <= 0: # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
count = 0
return result
5. 买卖股票的最佳时机 II
题目：
思路：
采用贪心策略，局部最优：收集每天的正利润，全局最优：求得最大利润。
代码：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
result = 0
num = 0
for i in range(len(prices) - 1):
num = prices[i + 1] - prices[i]
if num > 0:
result += num
return result
6. 跳跃游戏
题目：
思路：
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
代码：
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0
if len(nums) == 1: return True
i = 0
# python不支持动态修改for循环中变量,使用while循环代替
while i <= cover:
cover = max(i + nums[i], cover)
if cover >= len(nums) - 1: return True
i += 1
return False
7. 跳跃游戏 II
题目：
思路：
理解本题的关键在于：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点，这个范围内最少步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。
代码：
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) == 1:
return 0
result = 0
max_cover = 0
cur = 0
while 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 += 1
return result
result += 1
return 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 = 0
for i in range(len(nums)):
if k > 0 and nums[i] < 0:
nums[i] = -nums[i]
k -= 1
if 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小于0
start = i + 1 # 起始位置更新为i+1
curSum = 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 = 0
for i in range(1,len(ratings)): # 从左往右
if ratings[i] > ratings[i - 1]:
geting[i] = geting[i - 1] + 1
for 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 = 0
ten = 0
for bill in bills:
# 情况一：收到5美元
if bill == 5:
five += 1
# 情况二：收到10美元
if bill == 10:
if five <= 0:
return False
ten += 1
five -= 1
# 情况三：收到20美元
if bill == 20:
# 先尝试使用10美元和5美元找零
if five > 0 and ten > 0:
five -= 1
ten -= 1
#twenty += 1
# 如果无法使用10美元找零，则尝试使用三张5美元找零
elif five >= 3:
five -= 3
else:
return False
return 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 0
points.sort(key=lambda x: x[0])
result = 1
for 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 0
intervals.sort(key=lambda x:(x[0],x[1]))
result = 0
for i in range(1,len(intervals)):
if intervals[i][0] < intervals[i - 1][1]:
result += 1
intervals[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] = i
result = []
start = 0
end = 0
for i, ch in enumerate(s):
end = max(end, last_occurrence[ch]) # 找到当前字符出现的最远位置
if i == end: # 如果当前位置是最远位置，表示可以分割出一个区间
result.append(end - start + 1)
start = i + 1
return 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] += 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
