Skip to main content

刻练库1

刻意练习题库1，抽取常见类型题，进行专项练习。

题目​

动态规划​

名称级别状态备注
70. 爬楼梯简单已解答
剑指 Offer 10- II. 青蛙跳台阶问题简单已解答
剑指 Offer 63. 股票的最大利润中等已解答
121. 买卖股票的最佳时机简单已解答
122. 买卖股票的最佳时机 II中等已解答
123. 买卖股票的最佳时机 III中等已解答
188. 买卖股票的最佳时机 IV困难已解答
剑指 Offer 47. 礼物的最大价值中等已解答

LRU​

名称级别状态备注
146. LRU 缓存中等已解答

递归​

名称级别状态备注
200. 岛屿数量中等已解答

链表​

名称级别状态备注
148. 排序链表中等已解答
147. 对链表进行插入排序中等已解答
206. 反转链表简单已解答
21. 合并两个有序链表简单已解答
23. 合并 K 个升序链表困难已解答
160. 相交链表简单已解答

二分查找​

名称级别状态备注
34. 在排序数组中查找元素的第一个和最后一个位置中等已解答

HASH 表​

名称级别状态备注
706. 设计哈希映射简单已解答
705. 设计哈希集合简单已解答

最大频率栈​

名称级别状态备注
895. 最大频率栈困难已解答

排序​

名称级别状态备注
75. 颜色分类中等已解答
912. 排序数组中等已解答
215. 数组中的第K个最大元素中等已解答
239. 滑动窗口最大值困难已解答
703. 数据流中的第 K 大元素中等已解答

二叉树​

名称级别状态备注
102. 二叉树的层序遍历中等已解答
94. 二叉树的中序遍历简单已解答
剑指 Offer 32 - III. 从上到下打印二叉树 III中等已解答
437. 路径总和 III中等已解答
124. 二叉树中的最大路径和困难已解答
235. 二叉搜索树的最近公共祖先中等已解答
236. 二叉树的最近公共祖先中等已解答

栈​

名称级别状态备注
剑指 Offer 09. 用两个栈实现队列简单已解答

数组​

名称级别状态备注
56. 合并区间中等已解答
54. 螺旋矩阵中等已解答

解题​

70. 爬楼梯​


# range(3, i+1) and dp[i] = dp[i-1] + dp[i-2] 
class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 3: return n
        dp = [0] * (n+1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
           dp[i] = dp[i-1] + dp[i-2]

        return dp[-1]

剑指 Offer 10- II. 青蛙跳台阶问题​


# range(3, i+1) and dp[i] = dp[i-1] + dp[i-2] 
class Solution:
    def numWays(self, n: int) -> int:
        if n == 0: return 1
        if n <= 3: return n

        # DP 状态
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        dp[2] = 2

        # DP 方程
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[-1]%1000000007

121. 买卖股票的最佳时机​

(1) 最大值和最小值，迭代修改

def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1: return 0
        miniumu,maxiumu = prices[0], 0
        for i in range(1, len(prices)):
            maxiumu = max(maxiumu, prices[i] - miniumu)
            miniumu = min(miniumu, prices[i])
        return maxiumu

(2) DP 解题

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        
        k = 1

        # DP 状态初始化
        dp = [[[0,0] for _ in range(k + 1)] for _ in range(n)]

        # 初始化第一天DP状态
        for i in range(1, k+1):
            # 第0天，交易 K 次，持有一股
            dp[0][i][1] = -prices[0]
            # 第0天，交易 K 次，未持股票
            dp[0][i][0] = 0
        
        # DP 方程
        for i in range(1, n):
            for j in range(1, k + 1):
                # 未持股票
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                # 持有一股
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j - 1][0] - prices[i])

        return dp[-1][k][0]

122. 买卖股票的最佳时机 II​

# 交易任意次数
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0: return 0

        # DP 状态定义
        dp = [[0, 0] for _ in range(n)]

        # 第0天，未持股票
        dp[0][0] = 0
        # 第0天，持有股票
        dp[0][1] = -prices[0]

        # DP 方程
        for i in range(1, n):
            # 持有 0 股
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            # 持有 1 股
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

        return dp[-1][0]

123. 买卖股票的最佳时机 III​

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        
        k = 2

        # DP 状态初始化
        dp = [[[0,0] for _ in range(k + 1)] for _ in range(n)]

        # 初始化第一天DP状态
        for i in range(1, k+1):
            # 第0天，交易 K 次，持有一股
            dp[0][i][1] = -prices[0]
            # 第0天，交易 K 次，未持股票
            dp[0][i][0] = 0
        
        # DP 方程
        for i in range(1, n):
            for j in range(1, k + 1):
                # 未持股票
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                # 持有一股
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j - 1][0] - prices[i])

        return dp[-1][k][0]

188. 买卖股票的最佳时机 IV​

通解（剑指 offer 63、121、122、123、309、188、714)

DP 方程：

  • 不交易 → dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  • 买入一股 → dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k - 1][0] - prices[i])
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n == 0: return 0

        # DP 状态定义
        dp = [[[0,0] for _ in range(k + 1)] for _ in range(n)]
        # DP 状态初始化：第0天，交易 k 次，持有 1 股；未持股就是 0
        for i in range(1, k+1):
            dp[0][i][1] = -prices[0] 
        
        # DP 方程
        for i in range(1, n):
            for j in range(1, k+1):
                # 未持股票
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                # 持有股票
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
        return dp[-1][k][0]

309. 最佳买卖股票时机含冷冻期​


714. 买卖股票的最佳时机含手续费​


剑指 Offer 47. 礼物的最大价值​

DP 方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

def maxValue(self, grid: List[List[int]]) -> int:
        if not grid[0]: return 0

        m = len(grid) # 行
        n = len(grid[0]) # 列
        
        # 创建一个二维数组用于保存每个格子的最大值
        # 创建一个二维数组 dp，用于保存到达每个格子的最大价值
        # dp = [[0] * n for _ in range(m)]
        dp = [[0 for i in range(n)] for _ in range(m)]

        # dp 初始化
        dp[0][0] = grid[0][0]
        # 初始化第一行和第一列的最大值
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        
        # 递推计算每个格子的最大价值
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        
        # 返回右下角格子的最大价值
        return dp[m-1][n-1]

146. LRU 缓存​

设计一个双向链表 + 哈希表（key→value）

class DLinkedNode:
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        # self.capacity = capacity
        # self.cache = collections.OrderedDict()
        # 使用伪头部和尾部节点
        self.cache = dict()
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        # if key not in self.cache:
        #     return -1
        # self.cache.move_to_end(key)
        # return self.cache[key]
        if key not in self.cache:
            return -1
        # 如果 key 存在，先通过哈希标定位，再移动到头部
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        # if key in self.cache:
        #     self.cache.move_to_end(key)
        # self.cache[key] = value
        # if len(self.cache) > self.capacity:
        #     self.cache.popitem(last=False)
        if key not in self.cache:
            # key 不存在，新建一个节点
            node = DLinkedNode(key, value)
            # 添加进 hash 表
            self.cache[key] = node
            # 添加进双向链表的头部
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                # 如果超出容量，删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # key 存在，先通过哈希表定位，在修改 value，并移动到头部
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
    
    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        
    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)
    
    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

200. 岛屿数量​

def numIslands(self, grid: List[List[str]]) -> int:
        if not grid[0]: return 0

        m, n = len(grid), len(grid[0])
        count = 0
        def dfs(i, j):
            # 递归终止条件：终止条件，边界，或者遇到水
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
                return
            # 染色
            grid[i][j] = '0'

            # 四个方向进行搜索：上、下、左、右
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(i, j)
        return count

148. 排序链表​

fast,slow 指针 → 一分为二 → 迭代l,r链表→合并有序链表

def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        
        # slow, fast 指针，把链表一分为二，分别排序
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        mid = slow.next
        slow.next = None
        left = self.sortList(head)
        right = self.sortList(mid)

        # 合并 2 个有序链表
        dummy = ListNode(0)
        cur = dummy
        while left and right:
            if left.val <= right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next

        # 合并完成，把剩余链表放到末尾    
        cur.next = left if left else right
        return dummy.next

147. 对链表进行插入排序​

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
    
        dummy = ListNode(0)  # 创建一个新的链表作为已排序部分的头节点
        dummy.next = head
        sorted_tail = head  # 已排序部分的尾节点
        
        while sorted_tail.next:
            curr = sorted_tail.next  # 当前要插入的节点
            
            if curr.val >= sorted_tail.val: # 如果已经有序，则继续查找
                sorted_tail = sorted_tail.next
            else:
                # 从头开始找可以存放的位置
                prev = dummy  
                
                while prev.next.val < curr.val:
                    prev = prev.next
                
                sorted_tail.next = curr.next
                curr.next = prev.next
                prev.next = curr
        
        return dummy.next  # 返回已排序部分的头节点

206. 反转链表​

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return head

        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

21. 合并两个有序链表​

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1

        # 排序
        prehead = ListNode(0)
        curr = prehead
        l1 = list1
        l2 = list2
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 if l1 else l2
        return prehead.next

23. 合并 K 个升序链表​

def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 分治合并：O(kn×logk) O(logk)
        # 实现一个两个有序链表合并的函数，堆 K 个链表进行拆分
        def mergeTwoLists(l1, l2):
            if not l1: return l2
            if not l2: return l1

            head = None
            if l1.val <= l2.val:
                head = l1
                head.next = mergeTwoLists(l1.next, l2)
            else:
                head = l2
                head.next = mergeTwoLists(l1, l2.next)
            return head
        n = len(lists)
        if n == 0: return None
        if n == 1: return lists[0]
        if n == 2:
            return mergeTwoLists(lists[0], lists[1])
        
        mid = n//2
        l1 = lists[:mid]
        l2 = lists[mid:]
        return mergeTwoLists(self.mergeKLists(l1), self.mergeKLists(l2))

160. 相交链表​

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB: return None
        # hash set
        hs = set()
        A = headA
        while A != None:
            hs.add(A)
            A = A.next
        
        B = headB
        while B != None:
            if B in hs:
                return B
            B = B.next
        return None
    
    # 双指针，O(m+n) O(1)
    def s1(self, headA, headB):
        if not headA or not headB: return None
        A = headA
        B = headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

34. 在排序数组中查找元素的第一个和最后一个位置​

Time: O(logN), Space = O(1)

二分查找位置，确定目标值，利用 start, end 变量左右找边界。

def searchRange(self, nums: List[int], target: int) -> List[int]:
        left,right = 0, len(nums) - 1
        start = end = -1
        while left <= right:
            mid = left + (right - left)//2
            if nums[mid] == target:
                start = end = mid
                # 判断 start 值
                while start > 0 and nums[start - 1] == target:
                    start -= 1
                # 判断 end 值
                while end < len(nums) - 1 and nums[end + 1] == target:
                    end += 1
                break
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return [start, end]

706. 设计哈希映射​

class MyHashMap:

    def __init__(self):
       self.buckets = 1024
       self.table = [[] for _ in range(self.buckets)]

    def put(self, key: int, value: int) -> None:
        hashkey = key % self.buckets
        for item in self.table[hashkey]:
            if item[0] == key:
                item[1] = value
                return
        self.table[hashkey].append([key, value])

    def get(self, key: int) -> int:
        hashkey = key % self.buckets
        for item in self.table[hashkey]:
            if item[0] == key:
                return item[1]
        return - 1

    def remove(self, key: int) -> None:
        hashkey = key % self.buckets
        for i, item in enumerate(self.table[hashkey]):
            if item[0] == key:
                self.table[hashkey].pop(i)

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

705. 设计哈希集合​

class MyHashSet:

    def __init__(self):
        self.set = []

    def add(self, key: int) -> None:
        if key not in self.set:
            self.set.append(key)

    def remove(self, key: int) -> None:
        if key in self.set:
            i = self.set.index(key)
            if i >= 0:
                self.set.pop(i)

    def contains(self, key: int) -> bool:
        if key in self.set:
            return True
        else:
            return False

895. 最大频率栈​

class FreqStack:

    def __init__(self):
        self.freq_dict = {}  # 记录每个元素的频率
        self.group_dict = {}  # 记录每个频率对应的元素列表
        self.max_freq = 0  # 当前出现的最大频率

    def push(self, x: int) -> None:
        # 更新元素的频率
        self.freq_dict[x] = self.freq_dict.get(x, 0) + 1
        freq = self.freq_dict[x]
        
        # 更新最大频率
        self.max_freq = max(self.max_freq, freq)
        
        # 将元素加入到对应频率的列表中
        if freq not in self.group_dict:
            self.group_dict[freq] = []
        self.group_dict[freq].append(x)

    def pop(self) -> int:
        # 从最大频率对应的列表中弹出元素
        x = self.group_dict[self.max_freq].pop()
        
        # 更新元素的频率
        self.freq_dict[x] -= 1
        
        # 如果最大频率对应的列表为空，更新最大频率
        if not self.group_dict[self.max_freq]:
            self.max_freq -= 1
        
        return x

75. 颜色分类​

def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def swap(nums, index1, index2):
            nums[index1], nums[index2] = nums[index2], nums[index1]
        
        size = len(nums)
        if size < 2:
            return
        zero = 0
        two = size
        i = 0
        while i < two:
            if nums[i] == 0:
                swap(nums, i, zero)
                i += 1
                zero += 1
            elif nums[i] == 1:
                i += 1
            else:
                two -= 1
                swap(nums, i, two)

912. 排序数组​

# merge sort O(nlogn) O(n)
def sortArray(self, nums: List[int]) -> List[int]:
        def mergeSort(nums):
            if len(nums) <= 1:
                return nums
            mid = len(nums) // 2
            left = mergeSort(nums[:mid])
            right = mergeSort(nums[mid:])
            return merge(left, right)

        def merge(left, right):
            i, j = 0, 0
            merged = []
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    merged.append(left[i])
                    i += 1
                else:
                    merged.append(right[j])
                    j += 1
            while i < len(left):
                merged.append(left[i])
                i += 1
            while j < len(right):
                merged.append(right[j])
                j += 1
            return merged
        return mergeSort(nums)

215. 数组中的第K个最大元素​

def findKthLargest(self, nums: List[int], k: int) -> int:
        # 小根堆，O(nlogk) O(k)
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

239. 滑动窗口最大值​

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        window = deque()

        for i in range(len(nums)):
            # 移除滑动窗口外的元素
            if window and window[0] <= i - k:
                window.popleft()

            # 保持队列中元素的降序排列
            while window and nums[window[-1]] <= nums[i]:
                window.pop()

            # 添加当前元素到队列
            window.append(i)

            # 获取当前滑动窗口的最大值
            if i >= k - 1:
                result.append(nums[window[0]])

        return result
    
    # 大顶堆，py heapq
    def s2(self, nums, k):
        n = len(nums)
        # py 默认优先队列是小根堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)

        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans

    # 暴力法：O(n*k) 超时
    def s1(self, nums, k):
        if not nums: return []
        if k == 1: return nums
        res = []
        left, right = 0, k
        while right <= len(nums):
            window_max = float("-inf") # 不能为 0，因为 num 可能是负数
            for i in range(left, right):
                window_max = max(window_max, nums[i])
            res.append(window_max)
            left += 1
            right += 1
        return res

703. 数据流中的第 K 大元素​

# log(K) O(1)
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = []
        
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        
        return self.heap[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

102. 二叉树的层序遍历​

  • 非递归的中序排序
    • 非递归：BFS
    • 递归：BFS
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        res = []
        def bfs(root):
            queue = collections.deque()
            queue.append(root)

            while queue:
                level = []
                for _ in range(len(queue)):
                    node = queue.popleft()
                    level.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                res.append(level)
        bfs(root)
        return res

94. 二叉树的中序遍历​

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 前序：左右根
        # 中序：左根右
        # 后序：根左右
        res = []
        def inOrder(node):
            if not node: return None
            inOrder(node.left)
            res.append(node.val)
            inOrder(node.right)
        inOrder(root)
        return res

剑指 Offer 32 - III. 从上到下打印二叉树 III​

def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        # bfs 按层打印，在反转数组
        res = []
        def bfs(root):
            queue = collections.deque()
            queue.append(root)
            
            state = True
            while queue:
                level = []
                for _ in range(len(queue)):
                    node = queue.popleft()
                    level.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                if state:
                    res.append(level)
                else:
                    res.append(level[::-1])
                state = False if state else True
        bfs(root)
        return res

437. 路径总和 III​

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def rootSum(root, targetSum):
            if not root: return 0
            ret = 0
            if root.val == targetSum:
                ret += 1
            ret += rootSum(root.left, targetSum - root.val)
            ret += rootSum(root.right, targetSum - root.val)
            return ret
        if not root: return 0
        ret = rootSum(root, targetSum)
        ret += self.pathSum(root.left, targetSum)
        ret += self.pathSum(root.right, targetSum)
        return ret

124. 二叉树中的最大路径和​

# O(N） O(N)
def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # 定义一个变量记录最大路径和的值，初始值设为负无穷大
        self.max_sum = float('-inf')

        def maxPathSumHelper(node):
            if not node:
                return 0

            # 递归计算左子树的最大路径和，若为负数则舍弃，取0
            left_sum = max(maxPathSumHelper(node.left), 0)

            # 递归计算右子树的最大路径和，若为负数则舍弃，取0
            right_sum = max(maxPathSumHelper(node.right), 0)

            # 计算当前节点的最大路径和，包括三种情况
            # 1. 只取当前节点的值
            # 2. 取当前节点的值加上左子树路径和
            # 3. 取当前节点的值加上右子树路径和
            current_sum = node.val + left_sum + right_sum

            # 更新最大路径和的值
            self.max_sum = max(self.max_sum, current_sum)

            # 返回当前节点的最大路径和（只能取左子树或右子树路径和的情况）
            return node.val + max(left_sum, right_sum)

        # 调用辅助函数进行递归计算
        maxPathSumHelper(root)

        return self.max_sum

235. 二叉搜索树的最近公共祖先​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root: return
        if not root or root == p or root == q: return root
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left,p,q)
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right,p,q)
        else:
            return root
    
    # 二叉树通用解法
    def s1(self, root, p, q):
        if not root: return None
        if root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        if not left:
            return right
        if not right:
            return left
        return None

236. 二叉树的最近公共祖先​

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root: return root
        if root == p or root == q: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        # 左子树、右子树都能找到结果，公共祖先为 root
        if left != None and right != None:
            return root
        # 左子树找到结果，公共祖先 left
        elif left != None:
            return left
        # 右子树找到结果，公共祖先 right
        elif right != None:
            return right
        # 没找到，返回 None
        return None

剑指 Offer 09. 用两个栈实现队列​

class CQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def appendTail(self, value: int) -> None:
        self.stack1.append(value)

    def deleteHead(self) -> int:
        if len(self.stack2) == 0:
            if len(self.stack1) == 0:
                return -1
            else:
                while self.stack1:
                    self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

56. 合并区间​

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

54. 螺旋矩阵​

# Time: O(N) Space: O(1)
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []
    
        m, n = len(matrix), len(matrix[0])
        top, bottom, left, right = 0, m - 1, 0, n - 1
        direction = 0
        result = []
        
        while top <= bottom and left <= right:
            if direction == 0:  # 向右
                for i in range(left, right + 1):
                    result.append(matrix[top][i])
                top += 1
            elif direction == 1:  # 向下
                for i in range(top, bottom + 1):
                    result.append(matrix[i][right])
                right -= 1
            elif direction == 2:  # 向左
                for i in range(right, left - 1, -1):
                    result.append(matrix[bottom][i])
                bottom -= 1
            else:  # 向上
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1
            
            direction = (direction + 1) % 4
        
        return result