数据结构（列表 / 字典 / 栈）模块（6 题）

错题 16：列表切片与浅拷贝（修改子列表导致原列表变化）

• 错题题干：给定嵌套列表matrix = [[1,2,3],[4,5,6],[7,8,9]]，执行sub = matrix[:2]后，修改sub[0][0] = 0，观察 matrix 的变化，并解释原因。
• 错误代码 / 操作：

matrix = [[1,2,3],[4,5,6],[7,8,9]]
sub = matrix[:2]  # 预期：sub是[[1,2,3],[4,5,6]]，修改sub不影响matrix
sub[0][0] = 0
print(matrix)  # 实际输出：[[0,2,3],[4,5,6],[7,8,9]]，原列表被修改

• 错误原因分析：1. 列表切片的浅拷贝特性：matrix[:2]是 “浅拷贝”，仅复制列表的 “外层元素引用”，而非内层列表的内容；sub 中的[1,2,3]和[4,5,6]与 matrix 中的对应子列表指向同一内存地址，修改 sub 的子列表元素，会同步修改 matrix；2. 混淆 “浅拷贝” 和 “深拷贝”：若需完全独立的子列表，需用深拷贝（如copy.deepcopy()）。
• 正确操作（深拷贝）：

import copy
matrix = [[1,2,3],[4,5,6],[7,8,9]]
# 方法1：深拷贝，完全复制内层列表
sub_deep = copy.deepcopy(matrix[:2])
sub_deep[0][0] = 0
print(matrix)  # 输出：[[1,2,3],[4,5,6],[7,8,9]]，原列表未修改

# 方法2：手动深拷贝（嵌套列表）
sub_manual = [row.copy() for row in matrix[:2]]  # 对每个子列表执行copy()
sub_manual[0][0] = 0
print(matrix)  # 输出：[[1,2,3],[4,5,6],[7,8,9]]

• 复盘总结：Python 中列表的切片（list[:]）、list.copy()均为浅拷贝，仅适用于 “非嵌套列表”；处理嵌套列表时，需用copy.deepcopy()或手动逐层拷贝；需理解 “引用” 和 “值” 的区别，避免因浅拷贝导致的数据同步修改错误。

错题 17：列表排序（sorted () 与 list.sort () 的区别）

• 错题题干：给定列表nums = [3,1,2]，执行nums.sort(reverse=True)和sorted(nums, reverse=True)，分别输出 nums 的结果，并解释两者区别。
• 错误代码 / 操作：

nums = [3,1,2]
sorted_nums = nums.sort(reverse=True)  # 预期：sorted_nums是[3,2,1]
print(sorted_nums)  # 实际输出：None
print(nums)  # 输出：[3,2,1]

nums2 = [3,1,2]
nums2_sorted = sorted(nums2, reverse=True)
print(nums2_sorted)  # 输出：[3,2,1]
print(nums2)  # 输出：[3,1,2]，原列表未修改

• 错误原因分析：1. 混淆sorted()和list.sort()的返回值与修改方式：list.sort()是 “原地排序”，直接修改原列表，返回值为 None；sorted()是 “非原地排序”，不修改原列表，返回排序后的新列表；2. 错误地将list.sort()的返回值赋值给变量，导致变量为 None。
• 正确操作（清晰区分）：

# 1. list.sort()：原地排序，无返回值（返回None），修改原列表
nums = [3,1,2]
nums.sort(reverse=True)  # 直接对nums排序，无返回值
print("nums after sort():", nums)  # 输出：nums after sort(): [3,2,1]

# 2. sorted()：非原地排序，返回新列表，原列表不变
nums2 = [3,1,2]
sorted_nums2 = sorted(nums2, reverse=True)  # 新列表赋值给sorted_nums2
print("sorted_nums2:", sorted_nums2)  # 输出：sorted_nums2: [3,2,1]
print("nums2 after sorted():", nums2)  # 输出：nums2 after sorted(): [3,1,2]

# 3. 扩展：对嵌套列表按指定键排序（如按子列表第二个元素排序）
matrix = [[2,3],[1,4],[3,1]]
matrix.sort(key=lambda x: x[1])  # 按子列表x[1]升序排序
print("matrix sorted by x[1]:", matrix)  # 输出：[[3,1],[2,3],[1,4]]

• 复盘总结：排序时需根据需求选择方法：若需保留原列表，用sorted()；若无需保留原列表，用list.sort()（效率更高，无额外内存消耗）；两者均支持key和reverse参数，key参数接受函数（如 lambda 表达式），用于指定排序依据。

错题 18：字典键的唯一性与不可变性

• 错题题干：尝试创建字典d = {[1,2]:"a", (3,4):"b", "key":"c"}，解释报错原因，并修改代码使其正确。
• 错误代码 / 操作：

d = {[1,2]:"a", (3,4):"b", "key":"c"}  # 运行报错：TypeError: unhashable type: 'list'

• 错误原因分析：1. 字典键的不可变性要求：Python 字典的键必须是 “可哈希（hashable）” 类型，即不可变类型（如 int、str、tuple、bool 等）；列表（list）是可变类型（可通过append()、pop()等修改），不可哈希，不能作为字典键；2. 元组（tuple）是不可变类型，可作为字典键（如(3,4)）。
• 正确代码（修改键为可哈希类型）：

# 方法1：将列表键改为元组（不可变类型）
d1 = {(1,2):"a", (3,4):"b", "key":"c"}
print(d1)  # 输出：{(1, 2): 'a', (3, 4): 'b', 'key': 'c'}

# 方法2：若需用列表作为“逻辑键”，可将列表转为字符串（不可变类型）
d2 = {str([1,2]):"a", (3,4):"b", "key":"c"}
print(d2)  # 输出：{'[1, 2]': 'a', (3, 4): 'b', 'key': 'c'}
# 取值时需同样转为字符串：print(d2[str([1,2])])→'a'

# 注意：字典键的唯一性（重复键会覆盖）
d3 = {"name":"Alice", "name":"Bob"}
print(d3)  # 输出：{'name': 'Bob'}，后定义的键覆盖前一个

• 复盘总结：字典键的核心特性是 “可哈希（不可变）” 和 “唯一性”：1. 不可变类型才能作为键，避免列表、字典等可变类型；2. 重复键会导致值被覆盖，定义字典时需确保键唯一；若需用可变数据作为 “索引”，可先转为不可变类型（如元组、字符串）。

错题 19：字典 get () 方法与 KeyError

• 错题题干：给定字典student = {"name":"Li Ming", "age":20}，尝试获取student["score"]和student.get("score")，解释两者区别，并获取 score 时返回默认值 80。
• 错误代码 / 操作：

student = {"name":"Li Ming", "age":20}
print(student["score"])  # 运行报错：KeyError: 'score'（键不存在）
print(student.get("score"))  # 输出：None（键不存在时返回None）

• 错误原因分析：1. 字典键访问的两种方式区别：① 直接用dict[key]：若键不存在，抛出 KeyError；② 用dict.get(key, default)：若键不存在，返回 default（默认 None），不报错；2. 原代码未处理 “score 键不存在” 的情况，直接访问导致报错。
• 正确代码（用 get () 处理不存在的键）：

student = {"name":"Li Ming", "age":20}

# 1. 获取score，不存在时返回默认值80
score = student.get("score", 80)
print("Score:", score)  # 输出：Score: 80

# 2. 对比直接访问（需用try-except捕获KeyError）
try:
    score_direct = student["score"]
except KeyError:
    score_direct = 80
print("Score (direct access):", score_direct)  # 输出：Score (direct access): 80

# 3. 扩展：获取嵌套字典的键（如student有"grade":{"math":90}，获取"english"）
student["grade"] = {"math":90}
english_score = student.get("grade", {}).get("english", 85)  # 先获取grade，不存在则返回空字典，再获取english
print("English Score:", english_score)  # 输出：English Score: 85

• 复盘总结：访问字典中 “可能不存在的键” 时，优先用get()方法（代码更简洁，无需 try-except）；get()的第二个参数是默认值，可根据需求设置（如数字、字符串、空列表等）；处理嵌套字典时，可链式调用get()，并在中间层级设置默认空字典（{}），避免因中间键不存在导致报错。

错题 20：栈的括号匹配（有效括号）

• 错题题干：给定字符串s，判断其中的括号是否有效（仅包含 '()'、'{}'、'[]'，且左括号必须与右括号匹配，顺序正确）。示例：s="()[]{}"→True；s="(]"→False；s="([)]"→False。
• 错误代码：

def is_valid(s):
    stack = []
    for char in s:
        if char in "([{":
            stack.append(char)
        else:
            # 错误1：未判断栈是否为空（如s=")"，栈为空，弹出会报错）
            top = stack.pop()
            # 错误2：匹配逻辑错误（如top是'(', char是'}'，应返回False，原代码未覆盖所有不匹配情况）
            if (top == '(' and char != ')') or (top == '[' and char != ']'):
                return False
    # 错误3：未判断栈是否为空（如s="(()"，栈中剩余'('，应返回False）
    return True

• 错误原因分析：1. 未处理 “栈为空时弹出” 的情况（如 s 以右括号开头，栈为空，stack.pop()会抛出 IndexError）；2. 匹配逻辑不完整：仅判断了 '()' 和 '[]'，遗漏了 '{}' 的不匹配情况；3. 未判断循环结束后栈是否为空（如左括号数量多于右括号，栈中残留左括号，括号无效）。
• 正确代码：

def is_valid(s):
    # 步骤1：定义括号匹配字典（右括号→左括号，便于栈顶匹配）
    bracket_map = {')': '(', '}': '{', ']': '['}
    stack = []
    
    for char in s:
        if char in bracket_map.values():  # 左括号，压入栈
            stack.append(char)
        elif char in bracket_map.keys():  # 右括号，需匹配栈顶
            # 情况1：栈为空（右括号多于左括号）→无效
            # 情况2：栈顶左括号与当前右括号不匹配→无效
            if not stack or stack.pop() != bracket_map[char]:
                return False
        else:
            # 情况3：包含非括号字符→无效
            return False
    
    # 循环结束后，栈为空（左括号数量=右括号数量）→有效，否则无效
    return len(stack) == 0

• 复盘总结：括号匹配是栈的经典应用，核心逻辑是 “左括号压栈，右括号弹栈匹配”；需用字典存储 “右括号→左括号” 的映射，简化匹配逻辑；需覆盖所有边界情况：① 栈为空时弹出；② 括号不匹配；③ 非括号字符；④ 栈残留左括号。

错题 21：单调栈（直方图最大矩形面积）

• 错题题干：给定直方图的高度数组heights（如 [2,1,5,6,2,3]），求直方图中能画出的最大矩形面积。示例：预期输出 10（高度 5 和 6 的矩形，宽度 2，面积 5×2=10；或高度 2 和 2 的矩形，宽度 5，面积 2×5=10）。
• 错误代码：

def largest_rectangle_area(heights):
    max_area = 0
    # 错误：暴力法，时间复杂度O(n²)，n=10000时超时；且未处理边界（如heights为空）
    for i in range(len(heights)):
        min_height = heights[i]
        for j in range(i, len(heights)):
            min_height = min(min_height, heights[j])
            area = min_height * (j - i + 1)
            if area > max_area:
                max_area = area
    return max_area

• 错误原因分析：1. 暴力法时间复杂度过高：O (n²)，对于 n 较大的测试用例（如 n=10⁴）会超时，不符合效率要求；2. 未使用单调栈的优化思路：单调栈可在 O (n) 时间内找到每个柱子的 “左侧第一个更短柱子” 和 “右侧第一个更短柱子”，从而计算以该柱子为高度的最大矩形面积。
• 正确代码（单调栈优化）：

def largest_rectangle_area(heights):
    if not heights:
        return 0
    stack = []  # 单调栈：存储柱子索引，保持索引对应的高度递增
    max_area = 0
    n = len(heights)
    
    for i in range(n):
        # 当栈不为空，且当前柱子高度<栈顶柱子高度→弹出栈顶，计算面积
        while stack and heights[i] < heights[stack[-1]]:
            # 弹出栈顶索引，获取当前计算的柱子高度
            top_idx = stack.pop()
            height = heights[top_idx]
            # 计算宽度：
            # 若栈为空→左侧无更短柱子，宽度=i；
            # 若栈不为空→宽度=i - 栈顶索引 - 1
            width = i if not stack else i - stack[-1] - 1
            area = height * width
            max_area = max(max_area, area)
        # 当前柱子高度≥栈顶，压入栈
        stack.append(i)
    
    # 处理栈中剩余的柱子（右侧无更短柱子，宽度为n - 栈顶索引 - 1）
    while stack:
        top_idx = stack.pop()
        height = heights[top_idx]
        width = n if not stack else n - stack[-1] - 1
        area = height * width
        max_area = max(max_area, area)
    
    return max_area

• 复盘总结：单调栈是解决 “找左右第一个更优元素” 类问题的高效工具（如直方图面积、接雨水），核心是 “维持栈的单调性（递增 / 递减）”，通过弹出栈顶元素时的 “左右边界计算” 得到结果；需理解 “栈中存储索引而非值” 的原因（便于计算宽度），以及 “剩余栈元素的处理”（右侧无更短柱子）。