LeetCode 100+ 题详解 - 完整刷题指南¶

def two_sum_brute(nums, target):
    """
    两数之和（暴力法）
    时间：O(n²)
    空间：O(1)
    """
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

def two_sum_hash(nums, target):
    """
    两数之和（哈希表）
    时间：O(n)
    空间：O(n)
    """
    # 创建哈希表：数字 → 索引
    num_to_index = {}

    for i, num in enumerate(nums):
        # 计算需要的补数
        complement = target - num

        # 检查补数是否已在哈希表中
        if complement in num_to_index:
            return [num_to_index[complement], i]

        # 将当前数字存入哈希表
        num_to_index[num] = i

    return []

def two_sum_two_pointers(nums, target):
    """
    两数之和（双指针，需排序）
    时间：O(n log n)
    空间：O(n)
    """
    # 创建带索引的数组
    nums_with_index = [(num, i) for i, num in enumerate(nums)]  # enumerate同时获取索引和值

    # 排序
    nums_with_index.sort()

    # 双指针
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums_with_index[left][0] + nums_with_index[right][0]

        if current_sum == target:
            return [nums_with_index[left][1], nums_with_index[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []

def max_profit_brute(prices):
    """
    买卖股票（暴力法）
    时间：O(n²)
    空间：O(1)
    """
    max_profit = 0
    n = len(prices)

    for i in range(n):
        for j in range(i + 1, n):
            profit = prices[j] - prices[i]
            max_profit = max(max_profit, profit)

    return max_profit

def max_profit(prices):
    """
    买卖股票（一次遍历）
    时间：O(n)
    空间：O(1)
    """
    if not prices:
        return 0

    min_price = prices[0]  # 最低价格
    max_profit = 0         # 最大利润

    for price in prices[1:]:
        # 更新最低价格
        min_price = min(min_price, price)

        # 更新最大利润
        profit = price - min_price
        max_profit = max(max_profit, profit)

    return max_profit

def max_sub_array(nums):
    """
    最大子数组和（Kadane算法）
    时间：O(n)
    空间：O(1)
    """
    if not nums:
        return 0

    # 当前子数组和
    current_sum = nums[0]
    # 最大子数组和
    max_sum = nums[0]

    for num in nums[1:]:
        # 选择：扩展当前子数组 vs 从当前数字重新开始
        current_sum = max(num, current_sum + num)

        # 更新最大值
        max_sum = max(max_sum, current_sum)

    return max_sum

def max_sub_array_divide(nums):
    """
    最大子数组和（分治法）
    时间：O(n log n)
    空间：O(log n)
    """
    def divide_conquer(left, right):
        if left == right:
            return nums[left]

        mid = (left + right) // 2

        # 左半部分的最大子数组和
        left_max = divide_conquer(left, mid)

        # 右半部分的最大子数组和
        right_max = divide_conquer(mid + 1, right)

        # 跨越中点的最大子数组和
        # 从中点向左扩展
        left_sum = float('-inf')
        current_sum = 0
        for i in range(mid, left - 1, -1):
            current_sum += nums[i]
            left_sum = max(left_sum, current_sum)

        # 从中点+1向右扩展
        right_sum = float('-inf')
        current_sum = 0
        for i in range(mid + 1, right + 1):
            current_sum += nums[i]
            right_sum = max(right_sum, current_sum)

        cross_max = left_sum + right_sum

        # 返回三者中的最大值
        return max(left_max, right_max, cross_max)

    if not nums:
        return 0

    return divide_conquer(0, len(nums) - 1)

def remove_duplicates(nums):
    """
    删除有序数组中的重复项（双指针）
    时间：O(n)
    空间：O(1)
    """
    if not nums:
        return 0

    # 慢指针：指向不重复的最后位置
    slow = 0

    # 快指针：遍历数组
    for fast in range(1, len(nums)):
        # 当快指针指向的元素与慢指针不同时
        if nums[fast] != nums[slow]:
            # 慢指针前进
            slow += 1
            # 复制新元素
            nums[slow] = nums[fast]

    # 返回长度（索引+1）
    return slow + 1

def rotate(nums, k):
    """
    轮转数组（三次翻转）
    时间：O(n)
    空间：O(1)
    """
    n = len(nums)
    k %= n  # 处理 k >= n 的情况

    def reverse(left, right):
        """翻转 nums[left:right+1]"""
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    # 三次翻转
    reverse(0, n - 1)      # 翻转整个数组
    reverse(0, k - 1)      # 翻转前k个元素
    reverse(k, n - 1)      # 翻转后n-k个元素

def rotate_extra_array(nums, k):
    """
    轮转数组（额外数组）
    时间：O(n)
    空间：O(n)
    """
    n = len(nums)
    k %= n

    # 创建新数组
    result = [0] * n

    for i in range(n):
        result[(i + k) % n] = nums[i]

    # 复制回原数组
    for i in range(n):
        nums[i] = result[i]

def product_except_self(nums):
    """
    除自身以外数组的乘积
    时间：O(n)
    空间：O(1)（不包括输出数组）
    """
    n = len(nums)
    answer = [1] * n

    # 计算左侧乘积
    left_product = 1
    for i in range(n):
        answer[i] = left_product
        left_product *= nums[i]

    # 计算右侧乘积并更新answer
    right_product = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right_product
        right_product *= nums[i]

    return answer

def three_sum(nums):
    """
    三数之和
    时间：O(n²)
    空间：O(1)
    """
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # 跳过重复的第一个元素
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 双指针
        left, right = i + 1, n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if current_sum == 0:
                result.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

            elif current_sum < 0:
                left += 1
            else:
                right -= 1

    return result

def search_matrix(matrix, target):
    """
    搜索二维矩阵II
    时间：O(m + n)
    空间：O(1)
    """
    if not matrix or not matrix[0]:
        return False

    m, n = len(matrix), len(matrix[0])

    # 从右上角开始
    row, col = 0, n - 1

    while row < m and col >= 0:
        current = matrix[row][col]

        if current == target:
            return True
        elif current > target:
            # 当前值太大，向左移动
            col -= 1
        else:
            # 当前值太小，向下移动
            row += 1

    return False

def merge(intervals):
    """
    合并区间
    时间：O(n log n)
    空间：O(1)
    """
    if not intervals:
        return []

    # 按区间起点排序
    intervals.sort(key=lambda x: x[0])  # lambda匿名函数：简洁的单行函数

    result = []
    current = intervals[0]

    for interval in intervals[1:]:  # 切片操作：[start:end:step]提取子序列
        # 如果有重叠（当前区间的起点 <= 上一个区间的终点）
        if interval[0] <= current[1]:
            # 合并：更新终点为两者中较大的
            current[1] = max(current[1], interval[1])
        else:
            # 无重叠，保存当前区间，开始新区间
            result.append(current)
            current = interval

    # 添加最后一个区间
    result.append(current)

    return result

def set_zeroes(matrix):
    """
    矩阵置零
    时间：O(m*n)
    空间：O(1)
    """
    if not matrix or not matrix[0]:
        return

    m, n = len(matrix), len(matrix[0])

    # 标记第一行和第一列是否有0
    first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))

    # 用第一行和第一列标记0的位置
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    # 根据标记置零
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    # 处理第一行和第一列
    if first_row_has_zero:
        for j in range(n):
            matrix[0][j] = 0

    if first_col_has_zero:
        for i in range(m):
            matrix[i][0] = 0

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    """
    反转链表（迭代）
    时间：O(n)
    空间：O(1)
    """
    prev = None
    current = head

    while current:
        # 保存下一个节点
        next_node = current.next
        # 反转指针
        current.next = prev
        # 移动指针
        prev = current
        current = next_node

    return prev

def reverse_list_recursive(head):
    """
    反转链表（递归）
    时间：O(n)
    空间：O(n)（递归栈）
    """
    if not head or not head.next:
        return head

    # 递归反转后面的链表
    new_head = reverse_list_recursive(head.next)

    # 反转当前节点和下一个节点的指针
    head.next.next = head
    head.next = None

    return new_head

def merge_two_lists(l1, l2):
    """
    合并两个有序链表
    时间：O(m + n)
    空间：O(1)
    """
    # 创建虚拟头节点
    dummy = ListNode(0)
    current = dummy

    # 比较并合并
    while l1 and l2:
        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

    return dummy.next

def has_cycle(head):
    """
    环形链表（快慢指针）
    时间：O(n)
    空间：O(1)
    """
    if not head or not head.next:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next      # 慢指针走1步
        fast = fast.next.next # 快指针走2步

        # 如果相遇，说明有环
        if slow == fast:
            return True

    return False

def detect_cycle(head):
    """
    环形链表II
    时间：O(n)
    空间：O(1)
    """
    if not head or not head.next:
        return None

    # 第1步：判断是否有环
    slow = head
    fast = head

    has_cycle = False
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            has_cycle = True
            break

    if not has_cycle:
        return None

    # 第2步：找到环的入口
    # 一个指针从head开始，一个从相遇点开始
    # 相同速度前进，相遇点就是环入口
    ptr1 = head
    ptr2 = slow

    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    return ptr1

def is_palindrome(head):
    """
    回文链表
    时间：O(n)
    空间：O(1)
    """
    if not head or not head.next:
        return True

    # 第1步：找到中点
    slow = head
    fast = head

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

    # 第2步：反转后半部分
    second_half = reverse_list(slow.next)

    # 第3步：比较前后两部分
    first_half = head
    result = True

    while second_half:
        if first_half.val != second_half.val:
            result = False
            break
        first_half = first_half.next
        second_half = second_half.next

    # 第4步：恢复链表（可选）
    slow.next = reverse_list(second_half)

    return result

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    """
    二叉树的最大深度
    时间：O(n)
    空间：O(h)
    """
    if not root:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    return max(left_depth, right_depth) + 1

def is_valid_bst(root):
    """
    验证二叉搜索树
    时间：O(n)
    空间：O(h)
    """
    def validate(node, low, high):
        if not node:
            return True

        # 检查当前节点值是否在范围内
        if not (low < node.val < high):
            return False

        # 递归检查左右子树
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))

    return validate(root, float('-inf'), float('inf'))

def is_symmetric(root):
    """
    对称二叉树
    时间：O(n)
    空间：O(h)
    """
    if not root:
        return True

    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False

        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right)

from collections import deque

def level_order(root):
    """
    层序遍历
    时间：O(n)
    空间：O(n)
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

def flatten(root):
    """
    二叉树展开为链表
    时间：O(n)
    空间：O(1)
    """
    if not root:
        return

    current = root

    while current:
        if current.left:
            # 找到左子树的最右节点
            rightmost = current.left
            while rightmost.right:
                rightmost = rightmost.right

            # 将右子树接到左子树的最右节点
            rightmost.right = current.right

            # 将左子树移到右子树
            current.right = current.left
            current.left = None

        # 移动到下一个节点
        current = current.right

def climb_stairs(n):
    """
    爬楼梯
    时间：O(n)
    空间：O(1)
    """
    if n <= 2:
        return n

    # dp[i] = dp[i-1] + dp[i-2]
    prev, curr = 1, 2

    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr

    return curr

def climb_stairs_fast(n):
    """
    爬楼梯（矩阵快速幂）
    时间：O(log n)
    空间：O(1)
    """
    def matrix_pow(mat, power):
        result = [[1, 0], [0, 1]]  # 单位矩阵

        while power:
            if power % 2 == 1:
                result = matrix_multiply(result, mat)
            mat = matrix_multiply(mat, mat)
            power //= 2

        return result

    def matrix_multiply(a, b):
        return [
            [a[0][0] * b[0][0] + a[0][1] * b[1][0],
             a[0][0] * b[0][1] + a[0][1] * b[1][1]],
            [a[1][0] * b[0][0] + a[1][1] * b[1][0],
             a[1][0] * b[0][1] + a[1][1] * b[1][1]]
        ]

    if n <= 2:
        return n

    mat = [[1, 1], [1, 0]]
    result = matrix_pow(mat, n - 1)

    return result[0][0]

def rob(nums):
    """
    打家劫舍
    时间：O(n)
    空间：O(1)
    """
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)

    # dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    prev2 = nums[0]           # dp[i-2]
    prev1 = max(nums[0], nums[1])  # dp[i-1]

    for i in range(2, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current

    return prev1

def coin_change(coins, amount):
    """
    零钱兑换
    时间：O(amount * len(coins))
    空间：O(amount)
    """
    # dp[i] = 凑成金额i所需的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 凑成金额0需要0个硬币

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

def length_of_lis(nums):
    """
    最长递增子序列（DP）
    时间：O(n²)
    空间：O(n)
    """
    if not nums:
        return 0

    n = len(nums)
    # dp[i] = 以nums[i]结尾的最长递增子序列长度
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

import bisect

def length_of_lis_binary(nums):
    """
    最长递增子序列（二分查找）
    时间：O(n log n)
    空间：O(n)
    """
    if not nums:
        return 0

    # tails[i] = 长度为i+1的递增子序列的最小末尾
    tails = []

    for num in nums:
        # 二分查找第一个 >= num 的位置
        idx = bisect.bisect_left(tails, num)

        if idx == len(tails):
            tails.append(num)
        else:
            tails[idx] = num

    return len(tails)

def num_squares(n):
    """
    完全平方数
    时间：O(n * sqrt(n))
    空间：O(n)
    """
    # dp[i] = 和为i的完全平方数的最少数量
    dp = [float('inf')] * (n + 1)
    dp[0] = 0

    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1

    return dp[n]

from collections import deque

def can_finish(num_courses, prerequisites):
    """
    课程表（拓扑排序）
    时间：O(V + E)
    空间：O(V + E)
    """
    # 构建邻接表和入度数组
    adj = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    # 将入度为0的节点加入队列
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])

    # BFS拓扑排序
    count = 0
    while queue:
        node = queue.popleft()
        count += 1

        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 如果所有节点都被访问，说明没有环
    return count == num_courses

def find_order(num_courses, prerequisites):
    """
    课程表II
    时间：O(V + E)
    空间：O(V + E)
    """
    # 构建邻接表和入度数组
    adj = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1

    # BFS拓扑排序
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 判断是否有环
    return result if len(result) == num_courses else []

def solve(board):
    """
    被围绕的区域
    时间：O(m * n)
    空间：O(m * n)
    """
    if not board or not board[0]:
        return

    m, n = len(board), len(board[0])

    def dfs(i, j):
        """标记与边界相连的O"""
        if i < 0 or i >= m or j < 0 or j >= n:
            return
        if board[i][j] != 'O':
            return

        # 标记为临时字符
        board[i][j] = 'T'

        # 递归标记四个方向
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    # 第1步：从边界开始，标记所有与边界相连的O
    for i in range(m):
        for j in range(n):
            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                if board[i][j] == 'O':
                    dfs(i, j)

    # 第2步：遍历整个矩阵
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                # 被包围的O，改为X
                board[i][j] = 'X'
            elif board[i][j] == 'T':
                # 与边界相连的O，恢复为O
                board[i][j] = 'O'

def merge(nums1, m, nums2, n):
    """
    合并两个有序数组
    时间：O(m + n)
    空间：O(1)
    """
    # 三个指针
    p1 = m - 1      # nums1的最后一个元素
    p2 = n - 1      # nums2的最后一个元素
    p = m + n - 1   # 合并后的最后一个位置

    # 从后向前合并
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # 复制nums2剩余元素
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

def first_bad_version(n):
    """
    第一个错误的版本
    时间：O(log n)
    空间：O(1)
    """
    left, right = 1, n

    while left < right:
        mid = left + (right - left) // 2

        if is_bad_version(mid):
            # mid是错误版本，第一个错误版本在[left, mid]
            right = mid
        else:
            # mid是正确版本，第一个错误版本在[mid+1, right]
            left = mid + 1

    return left

def search_insert(nums, target):
    """
    搜索插入位置
    时间：O(log n)
    空间：O(1)
    """
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

def search_matrix(matrix, target):
    """
    搜索二维矩阵
    时间：O(log(m * n))
    空间：O(1)
    """
    if not matrix or not matrix[0]:
        return False

    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1

    while left <= right:
        mid = left + (right - left) // 2
        # 将一维索引转换为二维坐标
        row = mid // n
        col = mid % n

        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

def search_range(nums, target):
    """
    查找元素的第一个和最后一个位置
    时间：O(log n)
    空间：O(1)
    """
    def find_left():
        """找第一个位置"""
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    def find_right():
        """找最后一个位置"""
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left - 1

    if not nums:
        return [-1, -1]

    left_idx = find_left()
    right_idx = find_right()

    if left_idx <= right_idx and right_idx < len(nums) and nums[left_idx] == target:
        return [left_idx, right_idx]

    return [-1, -1]

def find_peak_element(nums):
    """
    寻找峰值
    时间：O(log n)
    空间：O(1)
    """
    if not nums:
        return -1

    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[mid + 1]:
            # 峰值在[left, mid]
            right = mid
        else:
            # 峰值在[mid+1, right]
            left = mid + 1

    return left