错题 7：区间调度问题（最多不重叠区间）

• 错题题干：给定多个区间（如 [[1,2],[2,3],[3,4],[1,3]]），求最多能选出多少个互不重叠的区间。预期输出 3（选 [[1,2],[2,3],[3,4]]）。
• 错误代码：

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0
    # 错误：按区间“开始时间”排序，而非“结束时间”
    intervals.sort(key=lambda x: x[0])
    count = 1
    last_end = intervals[0][1]
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start >= last_end:  # 不重叠
            count +=1
            last_end = end
    return count

• 错误原因分析：1. 贪心策略错误：区间调度的最优贪心策略是 “按结束时间升序排序”（选结束早的区间，给后续留更多空间），若按开始时间排序，可能选到结束晚的区间，导致后续可选项减少（如示例中 [[1,3]] 结束晚，选它后只能再选 [[3,4]]，共 2 个，比最优解少 1 个）。
• 正确代码：

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0
    # 核心贪心策略：按区间结束时间升序排序（优先选结束早的，保留更多后续空间）
    intervals.sort(key=lambda x: x[1])
    count = 1
    last_end = intervals[0][1]  # 记录已选区间的最后结束时间
    for i in range(1, len(intervals)):
        curr_start, curr_end = intervals[i]
        if curr_start >= last_end:  # 当前区间与已选区间不重叠，选中
            count += 1
            last_end = curr_end  # 更新最后结束时间
    return count

• 复盘总结：贪心算法的关键是 “找到正确的贪心策略”，需验证策略的最优性（如区间调度按结束时间排序，可通过反证法证明：若存在更优解，必能替换为按结束时间选的解）；排序是贪心题的常用预处理步骤，需明确排序键值。

错题 8：Huffman 编码（最小带权路径长度）

• 错题题干：给定 n 个字符的权重（如 [2,3,5,7]），用 Huffman 编码求最小带权路径长度（WPL，即每个权重 × 路径长度的总和，路径长度为编码的位数）。预期输出：2×3 + 3×3 +5×2 +7×1 = 6+9+10+7=32（Huffman 树结构：7 为根左孩子，5 为根右孩子；5 的左孩子 3，右孩子 2；路径长度：7→1，5→2，3→3，2→3）。
• 错误代码：

import heapq
def huffman_wpl(weights):
    heapq.heapify(weights)  # 建立小根堆
    wpl = 0
    while len(heap) > 1:  # 错误：变量名错误，heap应为weights
        a = heapq.heappop(weights)
        b = heapq.heappop(weights)
        new_node = a + b
        wpl += new_node  # Huffman的WPL等于所有非叶子节点的和，此处逻辑正确，但变量名错误导致报错
        heapq.heappush(weights, new_node)
    return wpl

• 错误原因分析：1. 变量名拼写错误：while 循环中误写 “heap”（未定义），实际应为 “weights”（堆的变量名）；2. 未处理权重数量为 1 的情况（虽题干 n≥2，但代码应兼容，若 len (weights)=1，WPL=0，因无需编码）。
• 正确代码：

import heapq
def huffman_wpl(weights):
    if len(weights) <= 1:
        return 0  # 只有1个字符，无需编码，WPL=0
    heapq.heapify(weights)  # 转换为小根堆（每次取最小的两个权重合并）
    wpl = 0
    while len(weights) > 1:
        # 弹出两个最小权重
        min1 = heapq.heappop(weights)
        min2 = heapq.heappop(weights)
        # 合并后的新节点权重（非叶子节点），其值计入WPL
        merged = min1 + min2
        wpl += merged
        # 将合并节点推回堆
        heapq.heappush(weights, merged)
    return wpl

• 复盘总结：Huffman 编码的核心是 “小根堆 + 合并最小权重”，WPL 等于所有非叶子节点的权重和，需牢记该规律；代码中需注意堆的变量名一致性，且处理边界情况（如权重数量≤1）。

错题 9：找零问题（最少硬币数）

• 错题题干：给定硬币面额（如 [1,2,5]）和目标金额 amount，求最少需要多少枚硬币找零（硬币可无限使用）。示例：amount=11，预期输出 3（5+5+1 或 5+2+2+2，最少 3 枚）。
• 错误代码：

def coin_change(coins, amount):
    if amount == 0:
        return 0
    # 错误：贪心策略仅适用于“无后效性”的面额（如[1,5,10,25]），本题[1,2,5]虽可用，但代码逻辑有漏洞（如amount=11，先取最大5，再取5，再取1，共3枚，正确；但若面额为[1,3,4]，amount=6，贪心取4+1+1=3枚，实际最优为3+3=2枚）
    coins.sort(reverse=True)  # 按面额降序排序
    count = 0
    for coin in coins:
        if amount >= coin:
            num = amount // coin
            count += num
            amount -= num * coin
        if amount == 0:
            break
    return count if amount == 0 else -1  # 未考虑无法找零的情况（如coins=[2], amount=3）

• 错误原因分析：1. 贪心策略的局限性：本题给定的 [1,2,5] 面额满足 “贪心最优”（因大面额是小面额的倍数），但代码未说明策略适用范围，若面额改为 [1,3,4]，贪心会失效；2. 未明确 “贪心仅适用于特定面额”，且代码未处理 “无法找零” 的返回（如 coins=[2], amount=3，应返回 - 1）。
• 正确代码（贪心适用场景）：

def coin_change_greedy(coins, amount):
    """仅适用于“大面额是小面额倍数”的硬币系统（如[1,2,5,10]）"""
    if amount == 0:
        return 0
    # 按面额降序排序，优先用大面额
    coins.sort(reverse=True)
    count = 0
    remaining = amount
    for coin in coins:
        if remaining >= coin:
            num = remaining // coin
            count += num
            remaining -= num * coin
        if remaining == 0:
            break
    # 若剩余金额不为0，说明无法找零
    return count if remaining == 0 else -1

• 复盘总结：贪心算法并非万能，需明确其适用场景（如本题的特定硬币系统）；若题目未限定面额，需改用动态规划（如dp[i] = min(dp[i], dp[i-coin]+1)）；汇报时需说明 “贪心的适用条件”，体现思维严谨性。

错题 10：分发饼干（匹配最多孩子）

• 错题题干：有 m 个孩子，每个孩子的胃口值 g [i]（需至少 g [i] 大小的饼干），n 个饼干，每个饼干大小 s [j]，每个孩子最多分 1 个饼干，求最多能满足多少孩子。示例：g=[1,2,3]，s=[1,1]，预期输出 1；g=[1,2]，s=[1,2,3]，预期输出 2。
• 错误代码：

def find_content_children(g, s):
    g.sort()  # 孩子胃口升序
    s.sort()  # 饼干大小升序
    child = 0  # 已满足的孩子数
    cookie = 0  # 已尝试的饼干数
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:  # 饼干能满足孩子
            child += 1
        cookie += 1  # 错误：无论是否满足，饼干都只能用1次，此处逻辑正确，但原代码注释错误（原注释写“饼干能满足孩子时才移动cookie”，实际代码正确，此处假设原代码注释错误导致理解偏差）
    return child

• 错误原因分析：1. 注释与代码逻辑不符：代码中 “无论饼干是否满足孩子，cookie 都会 + 1”（正确，因饼干只能用 1 次），但原注释可能误写为 “只有满足时才移动 cookie”，导致后续复盘时误解逻辑；2. 未验证极端情况（如 g 为空或 s 为空，应返回 0）。
• 正确代码（带清晰注释）：

def find_content_children(g, s):
    """贪心策略：用最小的饼干满足最小胃口的孩子，最大化饼干利用率"""
    if not g or not s:
        return 0  # 边界：无孩子或无饼干，返回0
    # 双排序：孩子按胃口升序，饼干按大小升序
    g.sort()
    s.sort()
    child_idx = 0  # 当前待满足的孩子索引
    cookie_idx = 0  # 当前待尝试的饼干索引
    max_children = 0
    while child_idx < len(g) and cookie_idx < len(s):
        if s[cookie_idx] >= g[child_idx]:
            # 饼干能满足孩子，计数+1，同时移动孩子索引（下一个孩子）
            max_children += 1
            child_idx += 1
        # 无论是否满足，饼干都已尝试，移动饼干索引（下一个饼干）
        cookie_idx += 1
    return max_children

• 复盘总结：分发类贪心题的核心是 “排序 + 双指针”，通过 “最小资源满足最小需求” 最大化利用率；代码注释需清晰，避免因注释错误导致逻辑误解；需覆盖边界情况（空数组），确保代码鲁棒性。