文章

LeetCode Hot100 · 缺失 27 题完整补充

补齐两份算法模板中尚无独立代码的 27 道官方 Hot100 题,形成完整 100 题复习卡。

2026年8月31日 更新于 2026年8月31日 约 3 分钟

专题 算法与笔试训练 第 3 篇 / 共 8 篇

本文完整同步自个人求职工作区,更新于 2026-08-31。源文件及后续更新托管在 GitHub 仓库 llm-algo-job-notes。

本文补齐《Hot100 算法模板与决策术》和《Hot100 补充篇》中尚无独立代码的 27 道官方 Hot100 题。代码采用 LeetCode 核心函数形式,链表和树节点类型由平台提供。

11. 盛最多水的容器

题目卡:给定若干竖线的高度,选择两条线与横轴组成容器,求能盛水的最大面积。

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, (right - left) * min(height[left], height[right]))
        if height[left] <= height[right]:
            left += 1
        else:
            right -= 1
    return best

239. 滑动窗口最大值

题目卡:给定数组和窗口大小 k,返回窗口从左向右移动时每个位置的最大值。

from collections import deque

def max_sliding_window(nums, k):
    queue = deque()  # 下标单调递减队列
    answer = []
    for right, value in enumerate(nums):
        while queue and queue[0] <= right - k:
            queue.popleft()
        while queue and nums[queue[-1]] <= value:
            queue.pop()
        queue.append(right)
        if right >= k - 1:
            answer.append(nums[queue[0]])
    return answer

56. 合并区间

题目卡:给定若干区间,合并所有重叠区间并返回互不重叠的结果。

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals = sorted(intervals)
    merged = [intervals[0][:]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

160. 相交链表

题目卡:给定两个单链表的头节点,找出它们开始相交的节点;若不相交则返回空。

def get_intersection_node(head_a, head_b):
    a, b = head_a, head_b
    while a is not b:
        a = a.next if a else head_b
        b = b.next if b else head_a
    return a

234. 回文链表

题目卡:判断一个单链表的节点值序列是否为回文,并在判断后恢复链表。

def is_palindrome(head):
    if not head or not head.next:
        return True
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    prev, cur = None, slow.next
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    second_head = prev

    left, right = head, second_head
    result = True
    while right:
        if left.val != right.val:
            result = False
            break
        left, right = left.next, right.next

    prev, cur = None, second_head
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    slow.next = prev
    return result

141. 环形链表

题目卡:判断单链表中是否存在环。

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

142. 环形链表 II

题目卡:若单链表存在环,返回环的入口节点;否则返回空。

def detect_cycle_entry(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    finder = head
    while finder is not slow:
        finder = finder.next
        slow = slow.next
    return finder

2. 两数相加

题目卡:两个链表以逆序数字表示非负整数,返回它们相加后的逆序链表。

def add_two_numbers(l1, l2):
    dummy = tail = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        total = carry
        if l1:
            total += l1.val
            l1 = l1.next
        if l2:
            total += l2.val
            l2 = l2.next
        carry, digit = divmod(total, 10)
        tail.next = ListNode(digit)
        tail = tail.next
    return dummy.next

148. 排序链表

题目卡:在 O(n log n) 时间内将单链表按升序排列。

def sort_list(head):
    if not head or not head.next:
        return head

    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    right = slow.next
    slow.next = None
    left = sort_list(head)
    right = sort_list(right)

    dummy = tail = ListNode(0)
    while left and right:
        if left.val <= right.val:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left or right
    return dummy.next

23. 合并 K 个升序链表

题目卡:合并 k 个升序链表,返回一条升序链表。

import heapq

def merge_k_lists(lists):
    heap = []
    serial = 0
    for node in lists:
        if node:
            heapq.heappush(heap, (node.val, serial, node))
            serial += 1
    dummy = tail = ListNode(0)
    while heap:
        _, _, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, serial, node.next))
            serial += 1
    return dummy.next

226. 翻转二叉树

题目卡:交换二叉树中每个节点的左右子树,并返回根节点。

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

199. 二叉树的右视图

题目卡:返回从二叉树右侧观察时从上到下能看到的节点值。

from collections import deque

def right_side_view(root):
    if not root:
        return []
    queue, answer = deque([root]), []
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            if i == level_size - 1:
                answer.append(node.val)
    return answer

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

题目卡:二叉树中的路径可从任意节点开始和结束,求所有非空路径的最大节点值之和。

def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best

22. 括号生成

题目卡:给定括号对数 n,生成所有有效的括号组合。

def generate_parenthesis(n):
    answer = []

    def dfs(path, opened, closed):
        if len(path) == 2 * n:
            answer.append("".join(path))
            return
        if opened < n:
            path.append("(")
            dfs(path, opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            dfs(path, opened, closed + 1)
            path.pop()

    dfs([], 0, 0)
    return answer

131. 分割回文串

题目卡:将字符串分割成若干子串,使每个子串都是回文串,返回所有分割方案。

def partition_palindromes(s):
    answer, path = [], []

    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def dfs(start):
        if start == len(s):
            answer.append(path[:])
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end + 1])
                dfs(end + 1)
                path.pop()

    dfs(0)
    return answer

51. N 皇后

题目卡:在 n×n 棋盘放置 n 个皇后,使其互不攻击,返回所有不同布局。

def solve_n_queens(n):
    answer, queens = [], []
    columns, diagonals1, diagonals2 = set(), set(), set()

    def dfs(row):
        if row == n:
            board = []
            for col in queens:
                board.append("." * col + "Q" + "." * (n - col - 1))
            answer.append(board)
            return
        for col in range(n):
            if col in columns or row - col in diagonals1 or row + col in diagonals2:
                continue
            queens.append(col)
            columns.add(col); diagonals1.add(row - col); diagonals2.add(row + col)
            dfs(row + 1)
            queens.pop()
            columns.remove(col); diagonals1.remove(row - col); diagonals2.remove(row + col)

    dfs(0)
    return answer

74. 搜索二维矩阵

题目卡:矩阵每行递增且下一行首元素大于上一行尾元素,判断目标值是否存在。

def search_matrix_flat(matrix, target):
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols
    while left < right:
        mid = (left + right) // 2
        value = matrix[mid // cols][mid % cols]
        if value < target:
            left = mid + 1
        else:
            right = mid
    return left < rows * cols and matrix[left // cols][left % cols] == target

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

题目卡:在非递减数组中以 O(log n) 时间返回目标值的起始和结束下标。

def search_range(nums, target):
    def lower_bound(value):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < value:
                left = mid + 1
            else:
                right = mid
        return left

    left = lower_bound(target)
    right = lower_bound(target + 1) - 1
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    return [left, right]

153. 寻找旋转排序数组中的最小值

题目卡:在元素互不相同的旋转升序数组中,以 O(log n) 时间找出最小值。

def find_min_rotated(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

4. 寻找两个正序数组的中位数

题目卡:给定两个正序数组,在 O(log(m+n)) 时间内求合并后的中位数。

def find_median_sorted_arrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    left, right = 0, m
    half = (m + n + 1) // 2
    while left <= right:
        i = (left + right) // 2
        j = half - i
        a_left = nums1[i - 1] if i else float("-inf")
        a_right = nums1[i] if i < m else float("inf")
        b_left = nums2[j - 1] if j else float("-inf")
        b_right = nums2[j] if j < n else float("inf")
        if a_left > b_right:
            right = i - 1
        elif b_left > a_right:
            left = i + 1
        else:
            if (m + n) % 2:
                return max(a_left, b_left)
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
    raise ValueError("Input arrays must be sorted")

394. 字符串解码

题目卡:解码形如 k[encoded_string] 的字符串,其中括号可以嵌套。

def decode_string(s):
    stack = []
    current, number = "", 0
    for char in s:
        if char.isdigit():
            number = number * 10 + int(char)
        elif char == "[":
            stack.append((current, number))
            current, number = "", 0
        elif char == "]":
            prefix, repeat = stack.pop()
            current = prefix + current * repeat
        else:
            current += char
    return current

70. 爬楼梯

题目卡:每次可以爬1或2级台阶,求到达第 n 级共有多少种不同方法。

def climb_stairs(n):
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return current

139. 单词拆分

题目卡:判断字符串能否由字典中的一个或多个单词拼接而成,字典单词可重复使用。

def word_break(s, word_dict):
    words = set(word_dict)
    max_length = max(map(len, words), default=0)
    reachable = [False] * (len(s) + 1)
    reachable[0] = True
    for end in range(1, len(s) + 1):
        start_min = max(0, end - max_length)
        for start in range(start_min, end):
            if reachable[start] and s[start:end] in words:
                reachable[end] = True
                break
    return reachable[-1]

152. 乘积最大子数组

题目卡:给定整数数组,求乘积最大的非空连续子数组的乘积。

def max_product(nums):
    current_max = current_min = answer = nums[0]
    for value in nums[1:]:
        if value < 0:
            current_max, current_min = current_min, current_max
        current_max = max(value, current_max * value)
        current_min = min(value, current_min * value)
        answer = max(answer, current_max)
    return answer

32. 最长有效括号

题目卡:给定只含左右括号的字符串,求最长有效连续括号子串的长度。

def longest_valid_parentheses(s):
    stack = [-1]
    best = 0
    for index, char in enumerate(s):
        if char == "(":
            stack.append(index)
        else:
            stack.pop()
            if not stack:
                stack.append(index)
            else:
                best = max(best, index - stack[-1])
    return best

62. 不同路径

题目卡:机器人只能向右或向下移动,求从 m×n 网格左上角到右下角的不同路径数。

def unique_paths(m, n):
    dp = [1] * n
    for _ in range(1, m):
        for col in range(1, n):
            dp[col] += dp[col - 1]
    return dp[-1]

1143. 最长公共子序列

题目卡:给定两个字符串,求它们最长公共子序列的长度。

def longest_common_subsequence(text1, text2):
    if len(text1) < len(text2):
        text1, text2 = text2, text1
    dp = [0] * (len(text2) + 1)
    for char1 in text1:
        diagonal = 0
        for j, char2 in enumerate(text2, 1):
            above = dp[j]
            if char1 == char2:
                dp[j] = diagonal + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            diagonal = above
    return dp[-1]

原始文档:GitHub 源文件。

本页目录