代码随想录训练营【贪心算法篇】

贪心

注：本文代码来自于代码随想录

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

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

这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。

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

455.分发饼干

力扣455

Python

贪心 大饼干优先

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

注意，大饼干优先一定要先遍历胃口再判断饼干能不能满足。不能像下面这种写法：

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort()i = len(g) - 1result = 0for index in range(len(s) - 1, -1, -1):if i >= 0 and g[i] <= s[index]:i -= 1result += 1"""这样写，index也就是饼干一直在遍历，而最大的胃口由于最大的饼干不够大而没有被满足，所以i并不会-1，也就是说，虽然饼干一直在往前遍历，但是始终停留在最大的胃口。就连最大的饼干也无法满足最大的胃口，其他饼干更不可能"""return result

贪心 小饼干优先

class Solution:def findContentChildren(self, g, s):g.sort()  # 将孩子的贪心因子排序s.sort()  # 将饼干的尺寸排序index = 0for i in range(len(s)):  # 遍历饼干if index < len(g) and g[index] <= s[i]:  # 如果当前孩子的贪心因子小于等于当前饼干尺寸index += 1  # 满足一个孩子，指向下一个孩子return index  # 返回满足的孩子数目

注意，小饼干优先一定要先遍历饼干再判断饼干能不能满足胃口。不能像下面这种写法：

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:g.sort()s.sort()index = 0for i in range(len(g)):if index < len(s) and g[i] <= s[index]:index += 1"""这样写，i也就是胃口一直在遍历，而最小的胃口由于最小的饼干不够大而没有被满足，所以index并不会+1，也就是说，虽然胃口一直在往后遍历，但是始终停留在最小的饼干。最小的饼干就连最小的胃口也满足不了，其他胃口更满足不了"""return index

栈 大饼干优先

from collecion import deque
class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:#思路,饼干和孩子按从大到小排序,依次从栈中取出，若满足条件result += 1 否则将饼干栈顶元素重新返回 result = 0queue_g = deque(sorted(g, reverse = True))queue_s = deque(sorted(s, reverse = True))while queue_g and queue_s:child = queue_g.popleft()cookies = queue_s.popleft()if child <= cookies:result += 1else:queue_s.appendleft(cookies)return result

376. 摆动序列

力扣376

这道题目难度是中等，我个人感觉很难。

• 输入: [1,17,5,10,13,15,10,5,16,8]

• 输出: 7

• 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

• 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

  整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

  局部最优推出全局最优，并举不出反例，那么试试贪心！

  （为方便表述，以下说的峰值都是指局部峰值）

  实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

  这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点

  这是我们思考本题的一个大体思路，但本题要考虑三种情况：

  1. 情况一：上下坡中有平坡
  2. 情况二：数组首尾两端
  3. 情况三：单调坡中有平坡

Python

贪心（版本一）

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  # 注意这里，只在摆动变化的时候更新preDiff# 如果把preDiff = curDiff写在if的外面，会掉进第三种情况的陷阱里return result  # 返回最长摆动子序列的长度

贪心（版本二）

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:if len(nums) <= 1:return len(nums)  # 如果数组长度为0或1，则返回数组长度preDiff,curDiff ,result  = 0,0,1  #题目里nums长度大于等于1，当长度为1时，其实到不了for循环里去，所以不用考虑nums长度for i in range(len(nums) - 1):curDiff = nums[i + 1] - nums[i]if curDiff * preDiff <= 0 and curDiff !=0:  #差值为0时，不算摆动result += 1preDiff = curDiff  #如果当前差值和上一个差值为一正一负时，才需要用当前差值替代上一个差值return result

动态规划（版本一）

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:# 0 i 作为波峰的最大长度# 1 i 作为波谷的最大长度# dp是一个列表，列表中每个元素是长度为 2 的列表dp = []for i in range(len(nums)):# 初始为[1, 1]dp.append([1, 1])for j in range(i):# nums[i] 为波谷if nums[j] > nums[i]:dp[i][1] = max(dp[i][1], dp[j][0] + 1)# nums[i] 为波峰if nums[j] < nums[i]:dp[i][0] = max(dp[i][0], dp[j][1] + 1)return max(dp[-1][0], dp[-1][1])

动态规划（版本二）

class Solution:def wiggleMaxLength(self, nums):dp = [[0, 0] for _ in range(len(nums))]  # 创建二维dp数组，用于记录摆动序列的最大长度dp[0][0] = dp[0][1] = 1  # 初始条件，序列中的第一个元素默认为峰值，最小长度为1for i in range(1, len(nums)):dp[i][0] = dp[i][1] = 1  # 初始化当前位置的dp值为1for j in range(i):if nums[j] > nums[i]:dp[i][1] = max(dp[i][1], dp[j][0] + 1)  # 如果前一个数比当前数大，可以形成一个上升峰值，更新dp[i][1]for j in range(i):if nums[j] < nums[i]:dp[i][0] = max(dp[i][0], dp[j][1] + 1)  # 如果前一个数比当前数小，可以形成一个下降峰值，更新dp[i][0]return max(dp[-1][0], dp[-1][1])  # 返回最大的摆动序列长度

动态规划（版本三）优化

class Solution:def wiggleMaxLength(self, nums):if len(nums) <= 1:return len(nums)  # 如果数组长度为0或1，则返回数组长度up = down = 1  # 记录上升和下降摆动序列的最大长度for i in range(1, len(nums)):if nums[i] > nums[i-1]:up = down + 1  # 如果当前数比前一个数大，则可以形成一个上升峰值elif nums[i] < nums[i-1]:down = up + 1  # 如果当前数比前一个数小，则可以形成一个下降峰值return max(up, down)  # 返回上升和下降摆动序列的最大长度

53. 最大子序和

力扣53

Python

暴力法

class Solution:def maxSubArray(self, nums):result = float('-inf')  # 初始化结果为负无穷大count = 0for i in range(len(nums)):  # 设置起始位置count = 0for j in range(i, len(nums)):  # 从起始位置i开始遍历寻找最大值count += nums[j]result = max(count, result)  # 更新最大值return result

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

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

力扣122

Python:

贪心:

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

动态规划:

class Solution:def maxProfit(self, prices: List[int]) -> int:length = len(prices)dp = [[0] * 2 for _ in range(length)]dp[0][0] = -prices[0]dp[0][1] = 0for i in range(1, length):dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) #注意这里是和121. 买卖股票的最佳时机唯一不同的地方dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])return dp[-1][1]

55. 跳跃游戏

力扣55

注意题目的意思是：假设最多往后跳3步，那么跳1步，2步，3步都是可以的。

不去思考要跳几步，只看覆盖范围。

Python

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

## for循环
class Solution:def canJump(self, nums: List[int]) -> bool:cover = 0if len(nums) == 1: return Truefor i in range(len(nums)):if i <= cover:cover = max(i + nums[i], cover)if cover >= len(nums) - 1: return Truereturn False

45.跳跃游戏 II

力扣45

Python

贪心（版本一）

class Solution:def jump(self, nums):if len(nums) == 1:return 0cur_distance = 0  # 当前覆盖最远距离下标ans = 0  # 记录走的最大步数next_distance = 0  # 下一步覆盖最远距离下标for i in range(len(nums)):next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖最远距离下标if i == cur_distance:  # 遇到当前覆盖最远距离下标ans += 1  # 需要走下一步cur_distance = next_distance  # 更新当前覆盖最远距离下标（相当于加油了）if next_distance >= len(nums) - 1:  # 当前覆盖最远距离达到数组末尾，不用再做ans++操作，直接结束breakreturn ans

贪心（版本二）

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

贪心（版本三） 类似‘55-跳跃游戏’写法

class Solution:def jump(self, nums) -> int:if len(nums)==1:  # 如果数组只有一个元素，不需要跳跃，步数为0return 0i = 0  # 当前位置count = 0  # 步数计数器cover = 0  # 当前能够覆盖的最远距离while i <= cover:  # 当前位置小于等于当前能够覆盖的最远距离时循环for i in range(i, cover+1):  # 遍历从当前位置到当前能够覆盖的最远距离之间的所有位置cover = max(nums[i]+i, cover)  # 更新当前能够覆盖的最远距离if cover >= len(nums)-1:  # 如果当前能够覆盖的最远距离达到或超过数组的最后一个位置，直接返回步数+1return count+1count += 1  # 每一轮遍历结束后，步数+1

动态规划

class Solution:def jump(self, nums: List[int]) -> int:result = [10**4+1] * len(nums)  # 初始化结果数组，初始值为一个较大的数result[0] = 0  # 起始位置的步数为0for i in range(len(nums)):  # 遍历数组for j in range(nums[i] + 1):  # 在当前位置能够跳跃的范围内遍历if i + j < len(nums):  # 确保下一跳的位置不超过数组范围result[i + j] = min(result[i + j], result[i] + 1)  # 更新到达下一跳位置的最少步数return result[-1]  # 返回到达最后一个位置的最少步数

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

力扣1005

Python

贪心

class Solution:def largestSumAfterKNegations(self, A: List[int], K: int) -> int:A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组Afor i in range(len(A)):  # 第二步：执行K次取反操作if A[i] < 0 and K > 0:A[i] *= -1K -= 1if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反A[-1] *= -1result = sum(A)  # 第四步：计算数组A的元素和return result

134. 加油站

力扣134

这题感觉好难，贪心思路很妙。

Python

暴力法

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:for i in range(len(cost)):rest = gas[i] - cost[i]  # 记录剩余油量index = (i + 1) % len(cost)  # 下一个加油站的索引while rest > 0 and index != i:  # 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）rest += gas[index] - cost[index]  # 更新剩余油量index = (index + 1) % len(cost)  # 更新下一个加油站的索引if rest >= 0 and index == i:  # 如果以i为起点跑一圈，剩余油量>=0，并且回到起始位置return i  # 返回起始位置ireturn -1  # 所有起始位置都无法环绕一圈，返回-1

贪心（版本一）

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:curSum = 0  # 当前累计的剩余油量minFuel = float('inf')  # 从起点出发，油箱里的油量最小值for i in range(len(gas)):rest = gas[i] - cost[i]curSum += restif curSum < minFuel:minFuel = curSumif curSum < 0:return -1  # 情况1：整个行程的总消耗大于总供给，无法完成一圈if minFuel >= 0:return 0  # 情况2：从起点出发到任何一个加油站时油箱的剩余油量都不会小于0，可以从起点出发完成一圈for i in range(len(gas) - 1, -1, -1):rest = gas[i] - cost[i]minFuel += restif minFuel >= 0:return i  # 情况3：找到一个位置使得从该位置出发油箱的剩余油量不会小于0，返回该位置的索引return -1  # 无法完成一圈

贪心（版本二） 视频上是这种方法，比较好理解。

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

135. 分发糖果

力扣135

Python

class Solution:def candy(self, ratings: List[int]) -> int:candyVec = [1] * len(ratings) # 初始化# 从前向后遍历，处理右侧比左侧评分高的情况for i in range(1, len(ratings)):if ratings[i] > ratings[i - 1]:candyVec[i] = candyVec[i - 1] + 1# 从后向前遍历，处理左侧比右侧评分高的情况for i in range(len(ratings) - 2, -1, -1):if ratings[i] > ratings[i + 1]:candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1)# 统计结果result = sum(candyVec)return result

860.柠檬水找零

力扣860

Python

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

406.根据身高重建队列

力扣406

Python

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]))"""sort 方法中的 key 参数定义了排序规则：-x[0] 表示第一个维度取反，这样可以实现从高到低排序；x[1] 表示第二个维度按默认的从小到大排序。"""que = []# 根据每个元素的第二个维度k，贪心算法，进行插入 # people已经排序过了：同一高度时k值小的排前面。for p in people:que.insert(p[1], p)# 例如p[1] = k = 3,前面有3个人比p的h要大，所以插在索引为3也就是第四个位置。return que

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

力扣452

巧妙在更新右边界

Python

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

class Solution: # 不改变原数组def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key = lambda x: x[0])sl,sr = points[0][0],points[0][1]count = 1for i in points:if i[0]>sr:count+=1sl,sr = i[0],i[1]else:sl = max(sl,i[0])sr = min(sr,i[1])return count

435. 无重叠区间

力扣435

Python

贪心 基于左边界

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if not intervals:return 0intervals.sort(key=lambda x: x[0])  # 按照左边界升序排序count = 0  # 记录重叠区间数量for i in range(1, len(intervals)):if intervals[i][0] < intervals[i - 1][1]:  # 存在重叠区间intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  # 更新重叠区间的右边界count += 1return count

贪心 基于左边界 把452.用最少数量的箭引爆气球代码稍做修改

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

763.划分字母区间

力扣763

掌握enumerate的用法，返回索引和值

假设输入字符串 s 为 "abacb", 通过 for 循环后，字典 last_occurrence 的构建过程如下：

• 开始时，last_occurrence 是一个空字典 {}。
• 遍历第一个字符 'a'（索引 0），last_occurrence 更新为 {'a': 0}。
• 遍历第二个字符 'b'（索引 1），last_occurrence 更新为 {'a': 0, 'b': 1}。
• 遍历第三个字符 'a'（索引 2），last_occurrence 更新为 {'a': 2, 'b': 1}（注意，这里更新了 'a' 的位置为 2）。
• 遍历第四个字符 'c'（索引 3），last_occurrence 更新为 {'a': 2, 'b': 1, 'c': 3}。
• 遍历第五个字符 'b'（索引 4），last_occurrence 更新为 {'a': 2, 'b': 4, 'c': 3}（注意，这里更新了 'b' 的位置为 4）。

最终，last_occurrence 字典会变成 {'a': 2, 'b': 4, 'c': 3}，表示字符 'a' 最后一次出现的位置是索引 2，字符 'b' 最后一次出现的位置是索引 4，字符 'c' 最后一次出现的位置是索引 3。

Python

贪心（版本一）版本一其实就是C++的写法，只不过左右区间用的不是left，right而是start，end

class Solution:def partitionLabels(self, s: str) -> List[int]:last_occurrence = {}  # 存储每个字符最后出现的位置for i, ch in enumerate(s):"""for i, ch in enumerate(s) 使用 enumerate 函数同时遍历字符串 s 的索引 i 和对应的字符 ch。enumerate(s) 返回一个包含索引和值的元组 (i, ch)，这里的 i 是当前字符 ch 在字符串 s 中的索引位置。"""last_occurrence[ch] = i"""last_occurrence[ch] = i 将当前字符 ch 的最后出现位置更新为索引 i。每次遍历到一个字符时，都更新该字符在字典中的值为当前索引。这样，字典 last_occurrence 最终会记录每个字符在字符串 s 中最后一次出现的位置。"""result = []start = 0end = 0for i, ch in enumerate(s):end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间result.append(end - start + 1) # 返回区间长度start = i + 1 # 下一个区间的左端点return result

贪心（版本二）与452.用最少数量的箭引爆气球 (opens new window)、435.无重叠区间 (opens new window)相同的思路。

class Solution:def countLabels(self, s):# 初始化一个长度为26的区间列表，初始值为负无穷hash = [[float('-inf'), float('-inf')] for _ in range(26)]hash_filter = []for i in range(len(s)):if hash[ord(s[i]) - ord('a')][0] == float('-inf'):hash[ord(s[i]) - ord('a')][0] = ihash[ord(s[i]) - ord('a')][1] = ifor i in range(len(hash)):if hash[i][0] != float('-inf'):hash_filter.append(hash[i])return hash_filterdef partitionLabels(self, s):res = []hash = self.countLabels(s)hash.sort(key=lambda x: x[0])  # 按左边界从小到大排序rightBoard = hash[0][1]  # 记录最大右边界leftBoard = 0for i in range(1, len(hash)):if hash[i][0] > rightBoard:  # 出现分割点res.append(rightBoard - leftBoard + 1)leftBoard = hash[i][0]rightBoard = max(rightBoard, hash[i][1])res.append(rightBoard - leftBoard + 1)  # 最右端return res

56. 合并区间

力扣56

result[-1][1]：这是 result 列表中最后一个区间的右边界。C++的写法是result.back()[1]

Python

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]：这是 result 列表中最后一个区间的右边界。C++的写法是result.back()[1]# 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的result[-1][1] = max(result[-1][1], intervals[i][1])else:result.append(intervals[i])  # 区间不重叠return result

738.单调递增的数字

力扣738

虽然卡哥讲起来感觉很简单，但是我感觉并不容易写出来，看代码的时候第一遍也没看懂，手推了几个例子才明白过程。写代码更是漏洞百出。

在 Python 中，字符串是不可变的对象，这意味着字符串一旦创建，就不能直接修改它们的内容。具体来说，字符串中的字符不能通过索引赋值来改变。

        strNum = strNum[:i] + '9' + strNum[i + 1:]# strnum[i] = '9'是错的，字符串不支持元素操作

Python

暴力

class Solution:def checkNum(self, num):max_digit = 10while num:digit = num % 10if max_digit >= digit:max_digit = digitelse:return Falsenum //= 10return Truedef monotoneIncreasingDigits(self, N):for i in range(N, 0, -1):if self.checkNum(i):return ireturn 0

贪心（版本一）

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:]# 这里i = 1的时候第一项应该是空字符串，第二项是第0位减一。整个表达式做的是给首位减去1.# 将flag位置及之后的字符都修改为9，以保证最大的递增数字for i in range(flag, len(strNum)):strNum = strNum[:i] + '9' + strNum[i + 1:]# strnum[i] = '9'是错的，字符串不支持元素操作# 将最终的字符串转换回整数并返回return int(strNum)

贪心（版本二）

class Solution:def monotoneIncreasingDigits(self, N: int) -> int:# 将整数转换为字符串strNum = list(str(N))# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质for j in range(i, len(strNum)):strNum[j] = '9'# 将列表转换为字符串，并将字符串转换为整数并返回return int(''.join(strNum))

贪心（版本三）

class Solution:def monotoneIncreasingDigits(self, N: int) -> int:# 将整数转换为字符串strNum = list(str(N))# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质strNum[i:] = '9' * (len(strNum) - i)# 将列表转换为字符串，并将字符串转换为整数并返回return int(''.join(strNum))

贪心（版本四）精简

class Solution:def monotoneIncreasingDigits(self, N: int) -> int:strNum = str(N)        for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:# 将前一个字符减1，以保证递增性质# 使用字符串切片操作将修改后的前面部分与后面部分进行拼接strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)       return int(strNum)

968.监控二叉树

力扣968

经过分析，空节点只能是有覆盖的状态。

根节点无覆盖的话，要给它加一个摄像头

这题好难好难！

如果 result 被设置为一个整数（例如 result = 0），那么在递归函数中修改 result 的值（如 result += 1）只会修改当前作用域的变量，而不会影响外部变量。因此，result 的变化不会在不同的递归层级之间共享，导致最终结果不正确。

使用列表 [0] 作为 result，递归函数可以通过修改 result[0] 来更新摄像头的数量，这种修改在所有递归层级之间共享，确保计数的正确性。

Python

贪心（版本一）

class Solution:# Greedy Algo:# 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优# 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖def minCameraCover(self, root: TreeNode) -> int:# 定义递归函数result = [0]  # 用于记录摄像头的安装数量if self.traversal(root, result) == 0: # 情况4：如果根节点最终是无覆盖状态，就在根节点加一个摄像头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:# 错在把条件写成cur.leftreturn 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

贪心（版本二）利用elif精简代码

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 左节点覆盖，右节点无覆盖elif left == 0 or right == 0:result[0] += 1return 1# 情况3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头else:return 2