Python 刷题清单¶

# Time: O(n), Space: O(n)
def subarraySum(nums: list[int], k: int) -> int:
    count, prefix_sum = 0, 0
    prefix_sum_map = {0: 1}  # 兼容 nums=[3], k=3
    for num in nums:
        prefix_sum += num  # 计算前缀和
        if prefix_sum - k in prefix_sum_map:  # 查找是否存在
            count += prefix_sum_map[prefix_sum - k]  # 累计频率
        prefix_sum_map[prefix_sum] = prefix_sum_map.get(prefix_sum, 0) + 1  # 对前缀和值的出现次数统计

    return count

# Time: O(n), Space: O(n)
def twoSum(nums: list[int], target: int) -> list[int]:
    # 哈希表记录出现的元素及索引
    # 遍历 nums，如果 target - num 在哈希表中，返回索引
    # 否则将 num 加入哈希表

    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [i, seen[target - num]]
        seen[num] = i

    return []

# Time: O(n), Space: O(n)
def longestConsecutive(nums: list[int]) -> int:
    has = set(nums)  # 使用集合简化判断

    ans = 0
    for num in has:
        if num - 1 in has:  # 上一个数存在于哈希表，说明 num 不是序列的起点
            continue

        next_num = num + 1
        while next_num in has:  # 不断查找下一个序列是否在哈希表中
            next_num += 1

        ans = max(ans, next_num - num)

    return ans

# 排序解法
# Time: O(m*nlogn), Space: O(m*n)
def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = {}
    for s in strs:
        key = "".join(sorted(s))
        groups.setdefault(key, []).append(s)

    return list(groups.values())

# 计数解法
# Time: O(m*n), Space: O(m*n)
def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = {}
    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        key = tuple(count)  # 列表不可哈希，转为元组作为键
        groups.setdefault(key, []).append(s)

    return list(groups.values())

# Time: O(n), Space: O(1)
def maxArea(height: list[int]) -> int:
    max_area, left, right = 0, 0, len(height) - 1
    while left < right:
        area = (right - left) * min(height[left], height[right])  # 以较矮的作为高计算面积
        max_area = max(max_area, area)
        # 只移动较矮的一边
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

# Time: O(m+n), Space: O(1)
def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    p1, p2, tail = m - 1, n - 1, m + n - 1

    # 只需检查 p2 >= 0，因为 nums2 处理完后，nums1 剩余元素已在正确位置
    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[tail] = nums1[p1]
            p1 -= 1
        else:
            nums1[tail] = nums2[p2]
            p2 -= 1
        tail -= 1

# Time: O(n), Space: O(1)
def moveZeroes(nums: list[int]) -> None:
    slow = 0  # 并不能确定 nums[0] 是否为非零值
    for fast in range(len(nums)):  # fast 要从0开始遍历，否则可能遗漏首位的零值交换。首位是非零值会发生自己和自己交换
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

# Time: O(n), Space: O(1)
def removeDuplicates(nums: list[int]) -> int:
    slow = 0
    for fast in range(1, len(nums)):
        if nums[slow] != nums[fast]:
            slow += 1  # 注意要交换到 slow 的下一个位置
            nums[slow] = nums[fast]

    return slow + 1  # 注意差1问题

# Time: O(n), Space: O(n)
def lengthOfLongestSubstring(s: str) -> int:
    # 哈希表记录出现的元素及索引
    # 哈希表出现的元素，left 移动到哈希表中索引 +1 位置，否则右指针右移扩大窗口

    seen = {}
    left, right, max_win = 0, 0, 0
    while right < len(s):
        if s[right] in seen:
            left = seen[s[right]] + 1

        seen[s[right]] = right
        right += 1

        max_win = max(max_win, right - left)

    return max_win

# Time: O(n²), Space: O(1)
def threeSum(nums: list[int]) -> list[list[int]]:
    if len(nums) < 3:
        return []

    nums.sort()

    ans = []
    # 先固定第一个数
    for i in range(len(nums) - 2):
        # 提前剪枝：如果第一个数已经大于0，后面都是正数，不可能和为0
        if nums[i] > 0:
            break

        if i > 0 and nums[i] == nums[i - 1]:
            continue  # 跳过重复的第一个数

        # 用双指针让剩余两数之和与第一个数的和为0
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]

            # 注意此时已经排序
            if total < 0:  # 和太小，需要右移靠近较大数
                left += 1
            elif total > 0:  # 和太大，需要左移靠近较小数
                right -= 1
            else:  # 和为 0
                ans.append([nums[i], nums[left], nums[right]])

                # 跳过重复的第二个数
                while left < right and nums[left] == nums[left + 1]:
                    left += 1

                # 跳过重复的第三个数
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1

    return ans

# Time: O(n²), Space: O(1)
def longestPalindrome(s: str) -> str:
    start, max_len = 0, 0

    # 从中心向两侧扩展，返回回文长度
    def expand(l: int, r: int) -> None:
        nonlocal start, max_len
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        # 此时 [l+1, r-1] 是回文
        if r - l - 1 > max_len:
            start = l + 1
            max_len = r - l - 1

    for i in range(len(s)):
        # 无法预知以某个位置为中心的最长回文是奇数还是偶数长度，因此需要同时遍历两种情况，取最长的那个
        expand(i, i)      # 奇数长度回文（如 "aba"）
        expand(i, i + 1)  # 偶数长度回文（如 "abba"）

    return s[start:start + max_len]

# Time: O(n), Space: O(1)
def nextPermutation(nums: list[int]) -> None:
    # 从右往左找到第一个下降点 i
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # 从右往左找到第一个大于 nums[i] 的数 j
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        # 交换 i 和 j
        nums[i], nums[j] = nums[j], nums[i]

    # 反转 i 之后的部分
    left, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

# Time: O(n+m), Space: O(1)
def compareVersion(version1: str, version2: str) -> int:
    n, m = len(version1), len(version2)
    i, j = 0, 0
    while i < n or j < m:
        x = 0
        while i < n and version1[i] != '.':
            x = x * 10 + int(version1[i])
            i += 1
        i += 1  # 跳过点号

        y = 0
        while j < m and version2[j] != '.':
            y = y * 10 + int(version2[j])
            j += 1
        j += 1  # 跳过点号

        if x > y:
            return 1
        if x < y:
            return -1

    return 0

# Time: O(n), Space: O(1)
def reverseList(head: ListNode) -> ListNode:
    prev = None
    # 暂存、反转、移动
    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node

    return prev

# Time: O(n), Space: O(1)
def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
    dummy = ListNode(next=head)  # 可能从头结点开始反转

    prev = dummy
    for _ in range(1, left):
        prev = prev.next

    curr = prev.next
    for _ in range(left, right):  # 这段代码画个步骤图就出来了
        next_node = curr.next      # 暂存操作节点的移动路径
        curr.next = next_node.next # 摘下节点
        next_node.next = prev.next # 插到区间头部
        prev.next = next_node      # 移动操作的节点

    return dummy.next

# Time: O(n), Space: O(1)
def middleNode(head: ListNode) -> ListNode:
    if not head:
        return None

    slow, fast = head, head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next

    return slow

# Time: O(n), Space: O(1)
def hasCycle(head: ListNode) -> bool:
    slow, fast = head, head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:
            return True

    return False

# Time: O(n), Space: O(n)
def detectCycle(head: ListNode) -> ListNode:
    seen = set()
    while head:
        if head in seen:
            return head
        seen.add(head)
        head = head.next

    return None

# Time: O(m+n), Space: O(1)
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    pA, pB = headA, headB
    while pA != pB:
        pA = headB if pA is None else pA.next
        pB = headA if pB is None else pB.next

    return pA  # 没有相交时，遍历结束的链表最终指向 None

# Time: O(m+n), Space: O(1)
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    current = dummy

    # 注意该遍历需同时操作3个链表
    while l1 and l2:  # 注意是 and
        if l1.val < l2.val:      # 将较小的值挂载在新链表上
            current.next = l1
            l1 = l1.next         # 移动原链表
        else:
            current.next = l2
            l2 = l2.next
        current = current.next   # 移动新链表

    # 将链表剩余部分挂载，同时处理原链表为空
    current.next = l1 if l1 else l2

    # 注意返回的是 dummy.next
    return dummy.next

# Time: O(n), Space: O(1)
def reverseKGroup(head: ListNode, k: int) -> ListNode:
    dummy = ListNode(next=head)
    prev = dummy

    while True:
        tail = prev
        for _ in range(k):
            tail = tail.next
            if not tail:
                return dummy.next  # 不足 k 个时结束反转

        next_group = tail.next  # 下一组起始位置

        # 头插法局部反转链表
        cur = prev.next
        for _ in range(k - 1):
            next_node = cur.next
            cur.next = next_node.next
            next_node.next = prev.next
            prev.next = next_node

        # 区间反转完成后，准备下一组的反转，此时 curr 移动到了区间末尾
        cur.next = next_group
        prev = cur

# 归并解法
# Time: O(n·logk), Space: O(logk)
def mergeKLists(lists: list[ListNode]) -> ListNode:
    if not lists:
        return None

    return merge_range(lists, 0, len(lists) - 1)

def merge_range(lists: list[ListNode], left: int, right: int) -> ListNode:
    if left == right:
        return lists[left]

    mid = left + (right - left) // 2
    l1 = merge_range(lists, left, mid)
    l2 = merge_range(lists, mid + 1, right)

    return merge_two_lists(l1, l2)

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    cur = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next

    cur.next = l1 if l1 else l2

    return dummy.next

# 最小堆
# Time: O(n·logk), Space: O(k)
import heapq

def mergeKLists(lists: list[ListNode]) -> ListNode:
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode()
    cur = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next

        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

# Time: O(n·logn), Space: O(logn)
def sortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    mid = split(head)
    left = sortList(head)
    right = sortList(mid)

    return merge_two_lists(left, right)

def split(head: ListNode) -> ListNode:
    prev, slow, fast = head, head, head
    while fast and fast.next:
        prev, slow, fast = slow, slow.next, fast.next.next

    prev.next = None  # 注意需要切断链表

    return slow

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    curr = dummy
    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

    if l1:
        curr.next = l1
    if l2:
        curr.next = l2

    return dummy.next

# Time: O(n), Space: O(1)
def reorderList(head: ListNode) -> None:
    mid = middleNode(head)
    reversed_head = reverseList(mid)
    p1, p2 = head, reversed_head
    while p2.next:                             # 注意结束条件
        p1_next, p2_next = p1.next, p2.next    # 保存指针避免断链
        p1.next, p2.next = p2, p1_next         # 交叉连接
        p1, p2 = p1_next, p2_next              # 移动节点

def middleNode(head: ListNode) -> ListNode:
    slow, fast = head, head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next

    return slow

def reverseList(head: ListNode) -> ListNode:
    prev = None
    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node

    return prev

# Time: O(1) per get/put, Space: O(capacity)
class Node:  # 内部实现，不允许外部访问
    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 = {}               # 哈希表：key -> 链表节点
        self.head = Node()            # 虚拟头节点（最近使用）
        self.tail = Node()            # 虚拟尾节点（最久未使用）
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # 将节点移到头部（标记为最近使用）
            self._move_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 更新已存在的节点
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            # 创建新节点
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)

            # 检查容量，必要时删除最久未使用的节点
            if len(self.cache) > self.capacity:
                removed = self._remove_tail()
                del self.cache[removed.key]

    # 辅助方法：将节点添加到头部
    # 画一个三角插入图形理解分析：先把新节点与左右节点相连，再把右侧节点指向新节点，最后把head指向新节点。插入头部的节点操作要基于 head。
    def _add_to_head(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    # 辅助方法：移除节点
    def _remove_node(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    # 辅助方法：将节点移到头部
    def _move_to_head(self, node: Node) -> None:
        self._remove_node(node)
        self._add_to_head(node)

    # 辅助方法：移除尾部节点
    def _remove_tail(self) -> Node:
        node = self.tail.prev
        self._remove_node(node)
        return node

# Time: O(n), Space: O(n)
def traversal(root: TreeNode) -> list[int]:
    if not root:
        return []

    # Preorder: 根 -> 左 -> 右
    # return [root.val] + traversal(root.left) + traversal(root.right)

    # Inorder: 左 -> 根 -> 右
    return traversal(root.left) + [root.val] + traversal(root.right)

    # Postorder: 左 -> 右 -> 根
    # return traversal(root.left) + traversal(root.right) + [root.val]

# Time: O(n), Space: O(n)
from collections import deque

def levelOrder(root: TreeNode) -> list[list[int]]:
    ans = []
    if not root:
        return ans

    queue = deque([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)

        ans.append(level)

    return ans

# Time: O(n), Space: O(n)
def preorderTraversal(root: TreeNode) -> list[int]:
    ans = []
    if not root:
        return ans

    stack = [root]
    while stack:
        node = stack.pop()

        ans.append(node.val)
        # 因为栈是先进后出，所以先压右节点
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return ans

# Time: O(n), Space: O(n)
def inorderTraversal(root: TreeNode) -> list[int]:
    ans = []
    stack = []

    curr = root
    while curr or stack:
        # 把从根节点到叶节点的左节点都压入栈
        while curr:
            stack.append(curr)
            curr = curr.left

        # 弹出栈中的节点（即从下往上遍历树）
        curr = stack.pop()

        ans.append(curr.val)

        # 左子树处理完处理右子树
        curr = curr.right

    return ans

# Time: O(n), Space: O(n)
def postorderTraversal(root: TreeNode) -> list[int]:
    ans = []
    stack = []
    prev = None

    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left

        # 查看栈顶不弹出
        curr = stack[-1]

        if not curr.right or curr.right == prev:
            stack.pop()
            ans.append(curr.val)
            prev = curr
            curr = None  # 重置，避免重复访问左子树
        else:
            curr = curr.right

    return ans

# Time: O(n), Space: O(n)
def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0

    left = maxDepth(root.left)
    right = maxDepth(root.right)

    return max(left, right) + 1

# Time: O(n), Space: O(n)
def isBalanced(root: TreeNode) -> bool:
    return dfs(root) != -1

# 返回树的高度，如果不平衡则返回 -1
# 后序遍历：先递归左右子树，返回时处理当前节点
def dfs(root: TreeNode) -> int:
    if not root:
        return 0

    # 先检查左、右子树
    left = dfs(root.left)
    right = dfs(root.right)
    if left == -1 or right == -1:
        return -1  # 左子树或右子树不平衡，提前终止

    # 检查当前节点是否平衡
    if abs(left - right) > 1:
        return -1  # 当前节点不平衡

    # 返回当前节点的高度（自底向上汇总信息）
    return max(left, right) + 1

# Time: O(n), Space: O(n)
def diameterOfBinaryTree(root: TreeNode) -> int:
    max_diameter = 0

    def depth(node: TreeNode) -> int:
        nonlocal max_diameter
        if not node:
            return 0

        # 后序遍历：先递归计算左右子树的深度
        left_depth = depth(node.left)
        right_depth = depth(node.right)

        # 当前节点的直径 = 左子树深度 + 右子树深度
        max_diameter = max(max_diameter, left_depth + right_depth)

        # 计算当前节点的深度
        return max(left_depth, right_depth) + 1

    depth(root)

    return max_diameter

# Time: O(n), Space: O(n)
def maxPathSum(root: TreeNode) -> int:
    max_sum = float('-inf')  # 初始化为最小值，因为节点值可能为负

    def max_gain(node: TreeNode) -> int:
        nonlocal max_sum
        if not node:
            return 0

        # 后序遍历：先递归计算左右子树的最大贡献
        # 如果子树贡献为负，则不选择该子树（取 0）
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # 以当前节点为"拐点"的路径和
        # 路径和 = 左子树贡献 + 右子树贡献 + 当前节点值
        current_path_sum = left_gain + right_gain + node.val
        max_sum = max(max_sum, current_path_sum)

        # 返回给父节点的最大贡献：只能选择左或右其中一条路径
        # 贡献 = 当前节点值 + max(左子树贡献, 右子树贡献)
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum

# Time: O(n), Space: O(n)
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    # 递归终止条件：
    # 1. 搜到底了（None）
    # 2. 找到目标节点（p 或 q）
    if not root or root == p or root == q:
        return root

    # 后序遍历：先递归左右子树
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    # 根据左右子树的返回值判断 LCA 位置
    # 情况 1：p 和 q 分散在左右两侧 → 当前节点就是 LCA
    if left and right:
        return root

    # 情况 2：p 和 q 都在左子树 → 返回左子树的结果
    if left:
        return left

    # 情况 3：p 和 q 都在右子树（或右子树找到一个）→ 返回右子树的结果
    return right

# 迭代解法(推荐)
# Time: O(h), Space: O(1)
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

    return None

# 递归解法
# Time: O(h), Space: O(h)
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
    return root

# Time: O(n), Space: O(n)
def isValidBST(root: TreeNode) -> bool:
    # prev 记录中序遍历中上一个访问的节点
    # 放在闭包外部，所有递归调用共享同一个变量
    prev = None

    # 定义闭包函数，自动捕获外部的 prev 变量
    def inorder(node: TreeNode) -> bool:
        nonlocal prev
        # 递归终止条件：空节点视为有效
        if not node:
            return True

        # 中序遍历：左 -> 根 -> 右
        # 1. 先递归检查左子树
        if not inorder(node.left):
            return False  # 左子树不合法，提前终止

        # 2. 检查当前节点：BST 的中序遍历必须严格递增
        if prev is not None and node.val <= prev.val:
            return False  # 不满足严格递增，不是 BST
        prev = node  # 更新 prev 为当前节点，供下一个节点比较

        # 3. 递归检查右子树
        return inorder(node.right)

    return inorder(root)