2026.8.10

146 LRU缓存

class LRUCache: def __init__(self, capacity: int): self.capacity=capacity self.cache=OrderedDict() def get(self, key: int) -> int: if key not in self.cache:return -1 self.cache.move_to_end(key,False) return self.cache[key] def put(self, key: int, value: int) -> None: self.cache[key]=value self.cache.move_to_end(key,False) if len(self.cache)>self.capacity: self.cache.popitem()

543 二叉树的直径

class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: ans=0 def dfs(node:Optional[TreeNode]) -> int: if node is None:return 0 l_len=dfs(node.left) r_len=dfs(node.right) nonlocal ans ans=max(ans,l_len+r_len) return max(l_len,r_len)+1 dfs(root) return ans

108 将有序数组转换为二叉搜索树

class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: if not nums: return None m=len(nums)//2 left=self.sortedArrayToBST(nums[:m]) right=self.sortedArrayToBST(nums[m+1:]) return TreeNode(nums[m],left,right)

200 岛屿数量

class Solution: def numIslands(self, grid: List[List[str]]) -> int: ans=0 m,n=len(grid),len(grid[0]) def dfs(i:int, j:int) -> None: if i<0 or j<0 or i>=m or j>=n or grid[i][j]!='1':return if grid[i][j]=='1':grid[i][j]=2 dfs(i-1,j) dfs(i+1,j) dfs(i,j-1) dfs(i,j+1) for i,row in enumerate(grid): for j,c in enumerate(row): if c=='1': dfs(i,j) ans+=1 return ans

98 验证二叉搜索树

class Solution: pre=-inf def isValidBST(self, root: Optional[TreeNode]) -> bool: if root is None:return True if not self.isValidBST(root.left):return False if root.val<=self.pre: return False self.pre=root.val return self.isValidBST(root.right)