目录
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:
return
dfs(root.right)
self.cnt-=1
if self.cnt==0:
self.res=root.val
return
dfs(root.left)
self.cnt=cnt
dfs(root)
return self.res
518. 零钱兑换 II
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp=[0]*(amount+1)
dp[0]=1
n=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 heapq
ans=[]
for num in stock:
heapq.heappush(ans,-num)
if len(ans)>cnt:
heapq.heappop(ans)
return [-num for num in ans]
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 None
if 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.right
while cur.left:
cur=cur.left
cur.left=root.left
return root.right
return root
59. 螺旋矩阵 II
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
left,right,up,down=0,n-1,0,n-1
matrix=[[0 for _ in range(n)] for _ in range(n)]
start,end=1,n*n
while start<=end:
for i in range(left,right+1):
matrix[up][i]=start
start+=1
up+=1
for i in range(up,down+1):
matrix[i][right]=start
start+=1
right-=1
for i in range(right,left-1,-1):
matrix[down][i]=start
start+=1
down-=1
for i in range(down,up-1,-1):
matrix[i][left]=start
start+=1
left+=1
return matrix
区别于54. 螺旋矩阵
LCR 127. 跳跃训练
class Solution:
def trainWays(self, num: int) -> int:
if num == 0:
return 1
if num==1 or num==2:
return num
dp=[0]*(num+1)
dp[1]=1
dp[2]=2
for 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+1
end=len(nums)-1
while start<end:
s=nums[i]+nums[start]+nums[end]
if abs(s-target)<abs(res-target):
res=s
if s>target:
end=end-1
elif s<target:
start+=1
else:
return s
return res
LCR 143. 子结构判断
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
# 以当前结点A为根结点的子树是否包含树B
def recur(A,B):
if not B:
return True
if not A or A.val !=B.val:
return False
return A.val ==B.val and recur(A.left,B.left) and recur(A.right,B.right)
if not A or not B:
return False
return 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=0
for i in range(n):
if nums[i]==0:
nums[i],nums[ptr]=nums[ptr],nums[i]
ptr+=1
for 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 <= 1000
if not matrix:
return False
rows=len(matrix)
cols=len(matrix[0])
i=0
j=cols-1
while j>=0 and i<rows:
if matrix[i][j]>target:
j-=1
elif matrix[i][j]<target:
i+=1
else:
return True
return False
