做网站要会哪些技术,电商网站大全,搭建一个商城网站,app代运营贪心
注#xff1a;本文代码来自于代码随想录
贪心算法一般分为如下四步#xff1a;
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
这个四步其实过于理论化了#xff0c;我们平时在做贪心类的题目 很难去按照这四步…贪心
注本文代码来自于代码随想录
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
这个四步其实过于理论化了我们平时在做贪心类的题目 很难去按照这四步去思考真是有点“鸡肋”。
做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
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 result376. 摆动序列
力扣376
这道题目难度是中等我个人感觉很难。 输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7 解释: 这个序列包含几个长度为 7 摆动序列其中一个可为[1,17,10,13,10,16,8]。 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。 整体最优整个序列有最多的局部峰值从而达到最长摆动序列。 局部最优推出全局最优并举不出反例那么试试贪心 为方便表述以下说的峰值都是指局部峰值 实际操作上其实连删除的操作都不用做因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了相当于是删除单一坡度上的节点然后统计长度 这就是贪心所贪的地方让峰值尽可能的保持峰值然后删除单一坡度上的节点 这是我们思考本题的一个大体思路但本题要考虑三种情况 情况一上下坡中有平坡情况二数组首尾两端情况三单调坡中有平坡
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 resultclass 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 result122.买卖股票的最佳时机 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 False45.跳跃游戏 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, cover1): # 遍历从当前位置到当前能够覆盖的最远距离之间的所有位置cover max(nums[i]i, cover) # 更新当前能够覆盖的最远距离if cover len(nums)-1: # 如果当前能够覆盖的最远距离达到或超过数组的最后一个位置直接返回步数1return count1count 1 # 每一轮遍历结束后步数1
动态规划
class Solution:def jump(self, nums: List[int]) - int:result [10**41] * 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(keylambda x: abs(x), reverseTrue) # 第一步按照绝对值降序排序数组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 result134. 加油站
力扣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为起点行驶一圈如果有rest0那么答案就不唯一了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 # 起始位置更新为i1curSum 0 # curSum重新从0开始累计if totalSum 0:return -1 # 总剩余油量totalSum小于0说明无法环绕一圈return start135. 分发糖果
力扣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 result860.柠檬水找零
力扣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 True406.根据身高重建队列
力扣406
Python
class Solution:def reconstructQueue(self, people: List[List[int]]) - List[List[int]]:# 先按照h维度的身高顺序从高到低排序。确定第一个维度# lambda返回的是一个元组当-x[0](维度h相同时再根据x[1]维度k从小到大排序people.sort(keylambda 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 que452. 用最少数量的箭引爆气球
力扣452
巧妙在更新右边界
Python
class Solution:def findMinArrowShots(self, points: List[List[int]]) - int:if len(points) 0: return 0points.sort(keylambda 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 resultclass 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:count1sl,sr i[0],i[1]else:sl max(sl,i[0])sr min(sr,i[1])return count435. 无重叠区间
力扣435
Python
贪心 基于左边界
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) - int:if not intervals:return 0intervals.sort(keylambda 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(keylambda 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) - result763.划分字母区间
力扣763
掌握enumerate的用法返回索引和值
假设输入字符串 s 为 abacb, 通过 for 循环后字典 last_occurrence 的构建过程如下
开始时last_occurrence 是一个空字典 {}。遍历第一个字符 a索引 0last_occurrence 更新为 {a: 0}。遍历第二个字符 b索引 1last_occurrence 更新为 {a: 0, b: 1}。遍历第三个字符 a索引 2last_occurrence 更新为 {a: 2, b: 1}注意这里更新了 a 的位置为 2。遍历第四个字符 c索引 3last_occurrence 更新为 {a: 2, b: 1, c: 3}。遍历第五个字符 b索引 4last_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的写法只不过左右区间用的不是leftright而是startend
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] ilast_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(keylambda 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 res56. 合并区间
力扣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(keylambda 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 result738.单调递增的数字
力扣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
