二刷复习
贪心篇
文章目录
455.分发饼干
分发饼干
这道题 我一开始想到思路了，就是排序之后，倒序遍历，大的饼干给大的孩子。我很容易想到了双指针，然后就写的一塌糊涂了。我发现我很难实现，大的饼干给大的孩子之后，下一次从次大的开始；并且我不知道谁当外循环比较好。
实际上，外层遍历必须是g数组，s数组倒序遍历，如果是大的能满足，下一次s数组从次大的开始；
两层循环巧用index
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
cnt = 0
m, index = len(g), len(s)-1
while m:
m -= 1
if index >= 0 and s[index] >= g[m]:
cnt += 1
index -= 1
return cnt
376. 摆动序列
摆动序列
这个题我一开始想的偏双指针了，我头脑混沌的想到了求两数的差值，但是没想到存下来这个差值。这个题应该转化成求峰值数量，两端天然就算成峰值点，我们遍历到倒数第二个结点，因为我们遍历一个点，就可以取nums[i],和nums[i+1], 记录一下当前的两点差值。如果说prev >= 0 and cur < 0 或者 prev <= 0 and cur > 0就可以更新cnt +1, 并且把prev更新成当前cur差值
贪心思想，遍历从第一个点到倒数第二个点，记录差值，找差值突变的波峰或者波谷
def wiggleMaxLength(self, nums: List[int]) -> int:
cur, prev, res = 0, 0, 1
for i in range(len(nums)-1):
cur = nums[i+1] - nums[i]
if (prev >= 0 and cur < 0) or (prev <= 0 and cur > 0):
res += 1
prev = cur
return res
dp解法
状态定义：dp[i][0] dp[i][1] 代表以i下标结尾的序列此时是波峰/波谷时，最长摆动序列的长度
状态转移：
如果说波峰 nums[i]>nums[j]: dp[i][0] = max(dp[i][0], dp[j][1]+1) j<i 波峰是由波谷转化来的
如果说波谷 nums[i]<nums[j]: dp[i][1] = max(dp[i][1], dp[j][0]+1) j<i 波谷是由波峰转化来的
初始化：
dp[0][1] 和 dp[0][0] 都应该等于1 ， dp数组是一个[[1,1],[,]…]这样的数组，其实这道题里应该直接把dp数组全初始化为[1,1], 这样的话如果摆动数组全是一样的值的话，返回的结果一直是1，不用特判这种情况
def wiggleMaxLength(self, nums: List[int]) -> int:
dp = [[1,1] for _ in range(len(nums))]
for i in range(1,len(nums)):
for j in range(i):
if nums[i] > nums[j]: dp[i][0] = max(dp[i][0], dp[j][1]+1)
if nums[i] < nums[j]: dp[i][1] = max(dp[i][1], dp[j][0]+1)
return max(dp[len(nums)-1][0],dp[len(nums)-1][1])
详细解法：
一刷
53.最大子数组和
这个贪心的点在于，最大子数组和，遍历到当前的数，如果前面是负数我们就不要了，从当前的继续来，可以用cnt记录一下累加的和，如果cnt > res我们更新一下，如果cnt < 0, 我们cnt 置0 从现在遍历位置从新开始累加
也可以用dp 记录一下当前位置的最大子数组和，更新思路是dp[i] = max(dp[i-1]+nums[i], nums[i])
122. 买卖股票的最佳时机 II
买卖股票的最佳时机 II
拆分利润到每天，只收集每两天之间的正利润
55.跳跃游戏
跳跃游戏
这个我是自己想到了贪心策略自己写出来了
贪心的点就是动态更新的是跳跃的范围，这个范围如果能到最后一位就行
我感觉比一刷抄的思路的代码看着容易理解
def canJump(self, nums: List[int]) -> bool:
if len(nums) == 1: return True
if len(nums) == 2 and nums[0] != 0: return True
max_step = nums[0]
for i in range(1,len(nums)-1):
if max_step >= i:
max_step = max(max_step, nums[i]+i)
if max_step >= len(nums)-1: return True
return False
45. 跳跃游戏 II
跳跃游戏 II
来先写一个带返回值的dfs
def jump(self, nums: List[int]) -> int:
def dfs(idx):
if idx >= len(nums) - 1:
return 0
ans = 10010
for i in range(1,nums[idx]+1):
ans = min(ans, dfs(idx+i)+1)
return ans
return dfs(0)
dfs记搜版本的
def jump(self, nums: List[int]) -> int:
self.mem = [-1] * (len(nums))
def dfs(idx):
if idx >= len(nums) - 1:
return 0
if self.mem[idx] != -1:
return self.mem[idx]
ans = 10010
for i in range(1,nums[idx]+1):
ans = min(ans, dfs(idx+i)+1)
self.mem[idx] = ans
return ans
return dfs(0)
贪心写法
贪心，维护两个cover一个是现在的cover, 一个是下一步的cover
如果说现在的cover到达不了终点，才跳下一步ans+1
在什么时候去判断呢？等i遍历到cur_cover的时候判断跳不跳
def jump(self, nums: List[int]) -> int:
cur_cover = 0
next_cover = 0
ans = 0
for i in range(len(nums)):
next_cover = max(next_cover, i+nums[i])
if i == cur_cover:
if cur_cover != len(nums)-1:
cur_cover = next_cover
ans += 1
if next_cover >= len(nums)-1: break
else: break
return ans
1005. K 次取反后最大化的数组和
K 次取反后最大化的数组和
这道题真是，能想到按绝对值大小排序，并且从大到小排，真不容易；如果不是这样的话，我们如果普通的排序，把负数部分变正之后如果k还有剩余并且是奇数的话，很难找到原本正数部分的最小值, 就算找到也会出现还要和负数部分的最大值比一个绝对值的情况
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort(key=abs, reverse=True) #按绝对值从大到小排列
for i in range(len(nums)):
if k > 0 and nums[i] < 0:
nums[i] = -nums[i]
k -= 1
if k % 2 == 1: #经历完之后，如果是没剩余就是 0 或者 剩偶数 都无所谓
nums[-1] = -nums[-1]
return sum(nums)
134.加油站
加油站
cursum = 0 #来维护一个gas[i]和cost[i]之间差的和
min_rest = 10001 #来维护一个剩余燃料值小的情况
#情况1, 消耗大于补充 怎么都不行
#情况2：从0开始模拟的，但是最小剩余从未小于0，说明从0走就行
#情况3：min_rest是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
cursum = 0
min_rest = 10001
for i in range(len(gas)):
rest = gas[i]-cost[i]
cursum += rest
if cursum < min_rest:
min_rest = cursum
if cursum < 0: return -1
if min_rest >= 0: return 0
#情况3
for i in range(len(gas)-1, -1, -1):
rest = gas[i] - cost[i]
min_rest += rest
if min_rest >= 0: return i
return -1
分发糖果
分发糖果
这个题的贪心是，遍历到的这个位置比相邻大的话，这个位置的糖果就比上一个高1（很抠吧）
需要维护一个糖果数组
如果想一次遍历就实现，会顾此失彼，所以要先从头遍历，确定右边大于左边的情况；+1就行
然后再从后向前遍历，确定左边大于右边的情况；取一个max(candies[i], candies[i+1]+1); 因为要保持第一次遍历的胜利成功，如果中间大要比两边都大
def candy(self, ratings: List[int]) -> int:
candies = [1] * len(ratings)
for i in range(1,len(ratings)):
if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1
for i in range(len(ratings)-2, -1, -1):
if ratings[i] > ratings[i+1]: candies[i] = max(candies[i], candies[i+1] + 1)
return sum(candies)
406.根据身高重建队列
根据身高重建队列
先按照身高排，要从高到低排，但是身高相同的话，要把第二个参数(前面有多少人)小的排前面
这样的话，lambda x:就是一个元组(-x[0], x[1]) 先按照身高排，身高高的排前面所以-x[0], 身高一样前面人少的排前面 x[1]。按照这个元组的规则去排
然后插的时候，新引入一个res [], 用函数list.insert(位置， 元素)
第一个是位置
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x: (-x[0], x[1]))
res = []
for p in people:
res.insert(p[1], p)
return res
860. 柠檬水找零
860.柠檬水找零
思路是模拟去做，主要判断5元够不够找
去遍历账单，维护两个变量，5元和10元的数量，如果说找不开的话return False; 如果说全遍历完没有return False, return True
贪心的点在于，在收到20这个情况里，必须先判断5元和10元同时存在的情况，如果没有再判断有没有3个五块，因为五块最通用所以最值钱
def lemonadeChange(self, bills: List[int]) -> bool:
five, ten = 0,0
for bill in bills:
if bill == 5: five += 1
elif bill == 10:
if five > 0:
five -= 1
ten += 1
else: return False
else:
if five > 0 and ten > 0:
five -= 1
ten -= 1
elif five > 2:
five -= 3
else: return False
return True
区间篇
452. 用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球
首先，根据左端点排序之后顺序遍历判断有几堆的思路很容易想到
其次，判断有几堆的思路就不容易想了对吧
可以说是，每一堆的第一个区间我们计数+1，然后维护最小右边界，如果遍历当前的区间左边界大于这个最小右边界了，等于说是新开了一堆，我们再计数+1；贪心的思想就融合在里面了，不多射
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: x[0])
cnt = 1
for i in range(1,len(points)):
if points[i][0] > points[i-1][1]: cnt += 1
else: points[i][1] = min(points[i][1], points[i-1][1])
return cnt
435. 无重叠区间
无重叠区间
这个题呢首先根据右边界排序很容易想，使得这些区间松散开，因为为了让右边区间更多互不重叠。
然后这个题其实也是求有多少重叠的堆，我们算出有多少重叠的堆，用总堆数一减，就知道要清楚的数量
然后还是用维护最小右边界的方法去做，和上题一样；
总结，无重叠用右边界排序，尽可能多重叠用左边界排序
763. 划分字母区间
划分字母区间
这道题一开始是没思路的
首先要维护一下每一个字母最后出现的位置，一共26个字母，开一个26长度的数组记录
dict = [0]*26
for i in range(len(s)):
dict[ord(s[i])-ord('a')] = i
然后呢，再去遍历S
去维护一个这一段里面能跑的最远的那个元素的右边界，如果说i遍历到这了，说明要分割了，分割的结果加进去，左边界下次从i+1开始
def partitionLabels(self, s: str) -> List[int]:
dict = [0]*26
for i in range(len(s)):
dict[ord(s[i])-ord('a')] = i
l, r = 0,0
res = []
for i in range(len(s)):
r = max(r, dict[ord(s[i])-ord('a')])
if i == r:
res.append(r-l+1)
l = i+1
return res
56.合并区间
合并区间
加进去，改变右端点
首先我要根据左边界去排序，为了判断重叠
我把第一个区间加进res列表里，从第二个区间开始判断，
如果说该区间的左端点大于等于res中最后一个区间的右端点，我们改变这个res[-1][1] = max(res[-1][1], i[1])#取一个右端点大的；如果说左端点大于res[-1]的右端点说明呢现在遍历的这个区间和之前的不重叠，那么就直接加进res
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for i in intervals[1:]:
if i[0] <= res[-1][1]: res[-1][1] = max(i[1], res[-1][1])
else: res.append(i)
return res
738.单调递增的数字
这道题有点那种减法列竖式，借位的概念了
就是说咱从后向前遍历，如果说前一位大于现在的这个i对应的值的话，不符合递增那么，
从i这一之后的所有数都变成9, 然后呢s[i-1]这一位-1(有点借位的意思了)
然后这样推到前头，整个数都被改完了就是答案了
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
s = list(str(n))
for i in range(len(s)-1, 0, -1):
if s[i-1] > s[i]: #前一位大于后一位不符合要求的话
s[i:] = (len(s)-i) * '9' #i包含i之后的位全部变成9
s[i-1] = str(int(s[i-1])-1) #第i-1位要-1
return int(''.join(s))
714.买卖股票的最佳时机含手续费
题目链接
这个贪心解法涉及的步骤太多 啊，记dp解法
只能一次持有一只股票的话，就是这样写，记录每一天持有/不持有能拥有的最大值
最后解的位置在不持有
dp = [[0] * 2 for _ in range(len(prices))]
dp[0][0] = -prices[0] - fee
for i in range(1, len(prices)):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]-fee) #持有
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) #不持有
return dp[-1][1]
968.监控二叉树
- 要从下往上遍历，即左右根。为什么，因为让叶子结点父节点开始放，然后隔着来最贪心
- #如果说是左右结点都有覆盖，那么我们当前这个node肯定无覆盖
- #如果说左右至少有一个无覆盖，当前这个结点要放摄像头
- #如果说左右至少一个有摄像头，当前这个结点一定有覆盖
- #rec完之后如果说根是0无覆盖状态，res += 1
class Solution:
def minCameraCover(self, root: Optional[TreeNode]) -> int:
res = 0
def rec(root):
nonlocal res
if root == None: return 2
left = rec(root.left)
right = rec(root.right)
# 转移状态，0 无覆盖 1 放摄像头 2 有覆盖
if left == 2 and right == 2: return 0
if left == 0 or right == 0:
res += 1
return 1
if left == 1 or right == 1:
return 2
if rec(root) == 0: res += 1
return res
文章评论