2024.5.9 —— LeetCode 高频题复盘

本文主要是介绍2024.5.9 —— LeetCode 高频题复盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LCR 174. 寻找二叉搜索树中的目标节点

题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:def dfs(root):if not root:returndfs(root.right)self.cnt-=1if self.cnt==0:self.res=root.valreturndfs(root.left)self.cnt=cntdfs(root)return self.res

518. 零钱兑换 II

题目链接

class Solution:def change(self, amount: int, coins: List[int]) -> int:dp=[0]*(amount+1)dp[0]=1n=len(coins)for i in range(n):for j in range(coins[i],amount+1):dp[j]+=dp[j-coins[i]]return dp[amount]

LCR 159. 库存管理 III

题目链接

class Solution:def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:import heapqans=[]for num in stock:heapq.heappush(ans,-num)if len(ans)>cnt:heapq.heappop(ans)return [-num for num in ans]

同面试题 17.14. 最小K个数

450. 删除二叉搜索树中的节点

题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:# 没找到要删除的结点if not root:return Noneif key>root.val:root.right=self.deleteNode(root.right,key)if key<root.val:root.left=self.deleteNode(root.left,key)if key==root.val:# 要删除的结点是叶子结点，左右结点为空if not root.left and not root.right:return None# 要删除的结点左结点为空，右结点不为空if not root.left and root.right:return root.right# 要删除的结点左结点不为空，右结点为空if root.left and not root.right:return  root.left# 要删除的结点左右结点均不为空if root.left and root.right:# 找到要删除结点的右孩子cur=root.rightwhile cur.left:cur=cur.leftcur.left=root.leftreturn root.rightreturn root

参考题解

59. 螺旋矩阵 II

题目链接

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:left,right,up,down=0,n-1,0,n-1matrix=[[0 for _ in range(n)] for _ in range(n)]start,end=1,n*nwhile start<=end:for i in range(left,right+1):matrix[up][i]=startstart+=1up+=1for i in range(up,down+1):matrix[i][right]=startstart+=1right-=1for i in range(right,left-1,-1):matrix[down][i]=startstart+=1down-=1for i in range(down,up-1,-1):matrix[i][left]=startstart+=1left+=1return matrix

区别于54. 螺旋矩阵

LCR 127. 跳跃训练

题目链接

class Solution:def trainWays(self, num: int) -> int:if num == 0:return 1if num==1 or num==2:return numdp=[0]*(num+1)dp[1]=1dp[2]=2for i in range(3,num+1):dp[i]=dp[i-1]+dp[i-2]return dp[num]%1000000007

注意本题与70. 爬楼梯有个小小的区别就是，n / num 的取值能不能为0。

16. 最接近的三数之和

题目链接

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:nums.sort()res=nums[0]+nums[1]+nums[2]for i in range(len(nums)):start=i+1end=len(nums)-1while start<end:s=nums[i]+nums[start]+nums[end]if abs(s-target)<abs(res-target):res=sif s>target:end=end-1elif s<target:start+=1else:return sreturn res

LCR 143. 子结构判断

题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:# 以当前结点A为根结点的子树是否包含树Bdef recur(A,B):if not B:return Trueif not A or A.val !=B.val:return Falsereturn A.val ==B.val and recur(A.left,B.left) and recur(A.right,B.right)if not A or not B:return Falsereturn recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

注意区别于 572. 另一棵树的子树，本题是判断子结构，只要包含这一部分就行，不管这一部分下面是否还有节点，而子树是包含该子树，该子树下面不能包含其他的节点，否则就不是包含该子树。
还有关联题目 100. 相同的树

75. 颜色分类

题目链接

class Solution:def sortColors(self, nums: List[int]) -> None:n=len(nums)ptr=0for i in range(n):if nums[i]==0:nums[i],nums[ptr]=nums[ptr],nums[i]ptr+=1for i in range(ptr,n):if nums[i]==1:nums[i],nums[ptr]=nums[ptr],nums[i]ptr+=1

LCR 121. 寻找目标值 - 二维数组

题目链接

class Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:# 0 <= n <= 1000# 0 <= m <= 1000if not matrix:return Falserows=len(matrix)cols=len(matrix[0])i=0j=cols-1while j>=0 and i<rows:if matrix[i][j]>target:j-=1elif matrix[i][j]<target:i+=1else:return Truereturn False