简介面向希望借经典赛题打磨算法与Python工程能力的开发者这份资源汇集了Advent of Code 2017至2020年全部题目的个人解答按年份与日期组织成可直接运行的代码仓库适合作为刷题参考、算法复盘与语言进阶的实战素材。压缩包共240个文件以152个Python源码为主体辅以83个input输入数据文件及少量图片与配置项整体约989KB体量轻便却覆盖了递归、图遍历、动态规划、矩阵与字符串处理、位运算、计算几何、网络流等多样题型。已有137人学习下载。读者可从中获取逐日拆分的完整解题实现观察如何借助itertools、collections、math等标准库简化逻辑并参考输入读取、算法组织与性能优化的写法理解生成器、列表推导式等特性的实际运用进而对照自身思路查漏补缺提升代码健壮性与问题拆解能力。1. 从一道“看起来会做却拿不到分”的题说起每年十二月都有一批人对着日历数日子不是等假期是等一套日历题上线。这套题就是 Advent of Code圈内人叫它 AoC。它从 2015 年一路出到 2020 年每年 25 天、每天两问题目从简单的字符串处理一路爬到图搜索、动态规划、状态压缩。很多人第一次做前两天顺风顺水第三天开始卡壳第七天直接放弃。问题不在不会写代码而在没摸清这套题的出题套路和评分逻辑。这场“考试”考什么考的是把一段自然语言描述翻译成可运行程序的能力考的是边界条件、输入规模、性能取舍。拿分方式很直接每天两问第一问通常是小规模模拟第二问把规模放大或规则加一层逼你换算法。适合谁适合已经会基本语法、想练真实问题拆解的人也适合准备技术面试、想拿一套完整题库练手的人。下面按考点分布、高频题型、真题演练、易错点、答题节奏五块拆开讲每一块都能直接拿去练。2. 考点分布2015 到 2020 六年题库的题型地图2.1 六年题目按算法类别拆开看AoC 的题面包装很花有精灵、有工厂、有飞船但剥掉故事外壳底层算法类别相当集中。把 2015 到 2020 六年的题目按类别归一下大致是这么个分布类别典型年份与天数出现频率拿分难度字符串解析与模拟每年第 13 天极高低网格遍历与 BFS/DFS2016 第 13 天、2019 第 15 天高中动态规划2015 第 17 天、2018 第 12 天中中高图最短路2016 第 24 天、2019 第 18 天中高状态压缩与位运算2015 第 7 天、2020 第 14 天中高数学与数论2017 第 15 天、2020 第 25 天中中解释器与虚拟机2017 第 23 天、2019 第 23 天低但必考高这张表最该记住的不是频率是“难度爬升曲线”。前三天几乎全是解析加模拟第四天开始上网格第七天前后必出一道需要换数据结构的题第二周开始出现图论和 DP最后几天往往是一道综合题。备考时按这个曲线分配精力比按年份顺序刷效率高得多。字符串解析这块六年里没有一年缺席。2015 年第 1 天数括号方向2016 年第 1 天算最短路径2017 年第 1 天做循环求和2018 年第 1 天求频率累加2019 年第 1 天算燃料2020 年第 1 天找两数之和。这些题的共同点是输入格式固定、规则明确考的是读题细不细不是算法强不强。很多人在这类题上翻车不是不会写是漏了负号、漏了换行、漏了空行。网格类题目是第二个高频区。2016 年第 13 天走迷宫2019 年第 15 天在无限网格上找最近目标2020 年第 11 天做座位模拟。这类题的通用套路是先把输入读成二维数组定义方向数组写一个neighbors函数然后套 BFS 或模拟循环。方向数组写成[(0,1),(1,0),(0,-1),(-1,0)]还是加上对角线取决于题面说的是四邻接还是八邻接这一步看错后面全错。动态规划在 AoC 里不会明着写“请用 DP”而是包装成“有多少种组合”“最少需要多少容器”。2015 年第 17 天给一组容器容量问凑出 150 升有多少种组合这是典型的子集和计数用一维 DP 数组倒序更新即可。2018 年第 12 天是细胞自动机规则固定但状态会重复考的是发现循环节而不是硬模拟。这类题的答题思路是先写暴力版本验证小输入再观察状态空间最后决定是加记忆化还是找周期。图最短路是拉开差距的地方。2016 年第 24 天要求遍历多个目标点本质是旅行商问题的简化版先对每个目标点跑一遍 BFS 求两两距离再对目标点做全排列。2019 年第 18 天是带钥匙和门的迷宫状态里必须带上“已收集钥匙集合”用位掩码压缩。这类题面试官最想听的是你怎么定义状态状态空间多大为什么 BFS 在这个状态图上成立。2.2 每天两问的设计逻辑与分值意识AoC 每天两问不是随便拆的。第一问通常给一个小规模输入规则直白暴力就能过第二问要么把输入放大几个数量级要么加一层约束逼你从“能跑”升级到“跑得动”。这个设计和技术面试里的“先写暴力解再优化”完全同构。拿 2015 年第 6 天举例。第一问给一组开灯关灯切换指令网格是 1000×1000直接开二维数组模拟每条指令遍历矩形区域能过。第二问把“切换”改成“亮度加减”规则变了但结构没变还是矩形区域更新。这时候如果还用逐格循环1000×1000×300 条指令在 Python 里会明显变慢。更稳的写法是二维差分数组每次矩形更新只改四个角最后做一次前缀和还原。这个“从逐格到差分”的跳跃就是第二问真正想考的东西。分值意识在这里很重要。AoC 没有官方分数但社区有完成时间和星数。25 天共 50 星前 10 天拿满不算本事第 15 天之后每多拿一星含金量明显上升。备考时建议按“前 10 天求稳、中间 10 天求准、最后 5 天求懂”分配时间。前 10 天练的是读题和边界中间 10 天练的是选型最后 5 天练的是把复杂状态讲清楚。提示不要按年份从头刷到尾。按类别刷比如集中一周只做网格类把 2016 第 13 天、2019 第 15 天、2020 第 11 天放在一起做你会发现方向数组、边界判断、访问标记这三件事反复出现形成肌肉记忆。3. 高频真题演练五道代表性题目的答题思路3.1 2015 年第 1 天括号方向与“负一层”判定题面给一长串括号左括号上楼右括号下楼从第 0 层出发。第一问求最终楼层第二问求第一次到达负一层时的位置。第一问是纯计数s.count(() - s.count())一行解决。第二问要的是“第一次”所以必须顺序扫描维护当前楼层一旦小于 0 就返回下标加一。def first_basement(s: str) - int: floor 0 for i, ch in enumerate(s, start1): floor 1 if ch ( else -1 if floor 0: return i # 题目要求从 1 开始计数 return -1这段代码的关键在enumerate(s, start1)。AoC 的位置类问题经常从 1 开始计数而 Python 默认从 0 开始差一位就是错。另一个易错点是“第一次”三个字有人先算完整串再回头找逻辑上也能做但多扫一遍没必要。面试里被问到类似“第一次出现”的题先顺序扫描、命中即返回是最稳的答法。3.2 2016 年第 13 天网格 BFS 与方向数组题面给一个迷宫网格#是墙.是路要求从起点走到终点最少几步。这是最标准的 BFS 模板题。from collections import deque def bfs(grid, start, goal): rows, cols len(grid), len(grid[0]) dirs [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右下左上四邻接 q deque([(start, 0)]) seen {start} while q: (r, c), dist q.popleft() if (r, c) goal: return dist for dr, dc in dirs: nr, nc r dr, c dc if 0 nr rows and 0 nc cols \ and grid[nr][nc] ! # and (nr, nc) not in seen: seen.add((nr, nc)) q.append(((nr, nc), dist 1)) return -1seen集合在入队时就标记不要等出队再标记否则同一个点会被重复入队队列膨胀。方向数组的顺序不影响正确性但影响调试时打印出来的路径形状建议固定一个顺序。边界判断写成0 nr rows这种链式比较比nr 0 and nr rows短且不容易写反。如果题面是八邻接方向数组扩成八个其余不动。3.3 2018 年第 12 天细胞自动机与循环节发现题面给一组初始植物状态和生长规则每代按左右邻居决定下一代。第一问模拟 20 代第二问模拟 500 亿代。第一问直接模拟用字符串或集合表示活细胞位置。第二问 500 亿次循环不可能硬跑必须发现规律这类一维自动机在有限规则下很快进入稳定平移状态即每代图案不变、整体左移或右移固定格数。def simulate(state: set, rules: dict, generations: int) - int: seen {} offset 0 for gen in range(generations): key (frozenset(state), offset) if key in seen: cycle gen - seen[key] remaining (generations - gen) % cycle for _ in range(remaining): state, offset step(state, rules, offset) return sum(p offset for p in state) seen[key] gen state, offset step(state, rules, offset) return sum(p offset for p in state)这里用(状态, 偏移)做键是因为图案可能整体平移只比状态不比偏移会误判。发现循环后不用跑完剩余代数直接取模跳过去。这类题在面试里常被包装成“大数模拟怎么优化”答题时先说“先跑小规模观察是否出现周期”再说“用哈希表记录状态和代数”最后说“取模跳过剩余步数”三步讲完就是完整答案。3.4 2019 年第 18 天带钥匙迷宫与状态压缩题面是一个迷宫里面有门和对应颜色的钥匙拿到钥匙才能开门问收集全部钥匙的最短步数。这是 BFS 的变体难点在状态定义。普通 BFS 的状态是位置(r, c)这里不够因为同一个位置在不同钥匙持有情况下意义不同。状态要扩成(r, c, keys)keys是一个位掩码第 i 位表示第 i 把钥匙是否已拿到。def bfs_keys(grid, start): rows, cols len(grid), len(grid[0]) all_keys 0 for r in range(rows): for c in range(cols): if grid[r][c].islower(): all_keys | 1 (ord(grid[r][c]) - ord(a)) dirs [(0, 1), (1, 0), (0, -1), (-1, 0)] q deque([(start[0], start[1], 0, 0)]) # r, c, keys, dist seen {(start[0], start[1], 0)} while q: r, c, keys, dist q.popleft() if keys all_keys: return dist for dr, dc in dirs: nr, nc r dr, c dc if not (0 nr rows and 0 nc cols): continue ch grid[nr][nc] if ch #: continue if ch.isupper() and not (keys (ord(ch.lower()) - ord(a)) 1): continue # 没有对应钥匙门打不开 nkeys keys | (1 (ord(ch) - ord(a))) if ch.islower() else keys state (nr, nc, nkeys) if state not in seen: seen.add(state) q.append((nr, nc, nkeys, dist 1)) return -1状态空间大小是行 × 列 × 2^钥匙数钥匙数一般不超过 26但实际题目里往往只有几个所以完全可搜。面试里被问“状态怎么设计”答“位置加已收集资源集合集合用位掩码压缩”再补一句“状态数上界是格子数乘资源子集数”基本就到位了。3.5 2020 年第 14 天位掩码与浮空地址题面是一个简单的位操作虚拟机指令有“掩码置位”“掩码清零”“浮空位”。第一问按固定掩码写内存第二问掩码里的X表示该位可以是 0 也可以是 1一个地址会展开成多个地址。第一问直接按位与、按位或。第二问要对每个X位做枚举生成所有可能地址。def expand(addr: int, mask: str) - list: results [addr] for i, ch in enumerate(reversed(mask)): if ch 1: results [r | (1 i) for r in results] elif ch X: results [r | (1 i) for r in results] \ [r ~(1 i) for r in results] return results这段代码从低位往高位扫遇到1就置位遇到X就分裂成两份。注意~在 Python 里是无限位取反配合使用时结果正确但如果直接打印会看到负数别慌。枚举顺序不影响最终求和但影响调试可读性。这类题考的是对位运算的熟练度面试里常问“怎么枚举一个掩码的所有子集”标准写法是sub mask; while sub: ...; sub (sub - 1) mask和这里的展开逻辑是同一类思维。4. 易错点五类反复失分的题与答法纠正4.1 输入解析漏掉负号和空行错在哪直接split()或splitlines()后转整数遇到-3或空行就抛异常或算错。 为什么错AoC 的输入文件经常带前后空行、负数、混合分隔符默认解析假设太强。 怎么答对先strip()去首尾空白按行过滤空行再用int()转换遇到混合分隔符用正则re.findall(r-?\d, line)一次性抽出所有整数。面试里被问“怎么健壮地读输入”答“先规范化再解析不假设格式完美”。4.2 BFS 在出队时才标记访问错在哪seen.add写在popleft()之后导致同一个点被多次入队。 为什么错BFS 的正确性依赖“入队即标记”晚标记会让队列里堆积重复状态小图看不出大图直接超时或爆内存。 怎么答对入队前检查并标记出队只负责扩展。这个顺序在面试白板上写的时候要刻意念出来“我先标记再入队避免重复。”4.3 动态规划数组更新方向写反错在哪0/1 背包类问题里内层循环从小到大更新一维 DP 数组。 为什么错从小到大更新会让同一物品被重复使用变成完全背包答案偏大。 怎么答对0/1 背包内层倒序完全背包内层正序写之前先问自己“这个物品能不能重复选”。AoC 2015 第 17 天是组合计数每个容器只能用一次必须倒序。4.4 把“第一次出现”当成“最终结果”错在哪先算完整串再回头找位置或者用index()找但没处理找不到的情况。 为什么错题面要的是过程中第一次满足条件的时刻不是结束后再判断。 怎么答对顺序扫描维护当前状态命中条件立即返回。找不到时返回约定的哨兵值并在注释里写清楚。4.5 大数模拟不做周期检测直接硬跑错在哪第二问代数到了十亿级还写for _ in range(10**9)。 为什么错这类题的设计意图就是让你发现规律硬跑既过不了也不体现能力。 怎么答对先跑前几百代把每代状态存进字典发现重复就计算周期用取模跳过剩余步数。面试里讲这一步时重点说“我怎么判断进入了周期”而不是只贴代码。5. 答题节奏把六年题库拆成四周训练计划四周怎么排直接给一张可执行的表。前提是每天能拿出两到三小时周末多一点。周次训练重点具体题目验收标准第 1 周解析与模拟各年第 13 天不看题解独立写完输入解析零异常第 2 周网格与 BFS2016 第 13 天、2019 第 15 天、2020 第 11 天能默写 BFS 模板并解释标记时机第 3 周DP 与位运算2015 第 17 天、2018 第 12 天、2020 第 14 天能说清状态定义和更新方向第 4 周图论综合2016 第 24 天、2019 第 18 天能讲清状态空间大小和为什么可搜这张表的用法不是打卡是“卡住就停”。某道题卡超过四十分钟先去看别人的思路但只看思路不看代码回来自己重写。重写时把关键决策点用注释标出来比如“这里用位掩码因为钥匙数少”“这里倒序因为每个容器只能用一次”。这些注释就是你以后复习的索引。还有一个习惯值得强制养成每道题写完先拿题面给的小样例跑一遍再自己构造一个边界样例比如空输入、单元素、全墙迷宫、零容量容器。AoC 的题面通常会给一两个样例但样例往往覆盖不到边界自己补一个能挡掉大部分翻车。面试场景下这套题库的用法又不一样。面试官不会让你现场做完整道 AoC但会问“给你一个网格怎么找最短路”“状态里要带什么信息”“规模大了怎么优化”。这时候答题结构比代码更重要先说输入输出和约束再说选什么算法再说状态怎么定义最后说复杂度和边界。AoC 的题面描述长、约束藏在故事里正好练“从自然语言里抽约束”的能力。我自己的血泪经验是早年刷这套题总想一天做完一整年结果第三天卡住就整段放弃。后来改成按类别集中练每类只做三道做完写一段“这类题的通用骨架”反而记得牢。从那以后我每次遇到新题都强制先问三件事输入规模多大、状态里必须带什么、有没有周期或重复。这三问走完大部分题的方向就定了。希望帮到你。本文还有配套的精品资源点击获取
简介面向希望借经典赛题打磨算法与Python工程能力的开发者这份资源汇集了Advent of Code 2017至2020年全部题目的个人解答按年份与日期组织成可直接运行的代码仓库适合作为刷题参考、算法复盘与语言进阶的实战素材。压缩包共240个文件以152个Python源码为主体辅以83个input输入数据文件及少量图片与配置项整体约989KB体量轻便却覆盖了递归、图遍历、动态规划、矩阵与字符串处理、位运算、计算几何、网络流等多样题型。已有137人学习下载。读者可从中获取逐日拆分的完整解题实现观察如何借助itertools、collections、math等标准库简化逻辑并参考输入读取、算法组织与性能优化的写法理解生成器、列表推导式等特性的实际运用进而对照自身思路查漏补缺提升代码健壮性与问题拆解能力。1. 从一道“看起来会做却拿不到分”的题说起每年十二月都有一批人对着日历数日子不是等假期是等一套日历题上线。这套题就是 Advent of Code圈内人叫它 AoC。它从 2015 年一路出到 2020 年每年 25 天、每天两问题目从简单的字符串处理一路爬到图搜索、动态规划、状态压缩。很多人第一次做前两天顺风顺水第三天开始卡壳第七天直接放弃。问题不在不会写代码而在没摸清这套题的出题套路和评分逻辑。这场“考试”考什么考的是把一段自然语言描述翻译成可运行程序的能力考的是边界条件、输入规模、性能取舍。拿分方式很直接每天两问第一问通常是小规模模拟第二问把规模放大或规则加一层逼你换算法。适合谁适合已经会基本语法、想练真实问题拆解的人也适合准备技术面试、想拿一套完整题库练手的人。下面按考点分布、高频题型、真题演练、易错点、答题节奏五块拆开讲每一块都能直接拿去练。2. 考点分布2015 到 2020 六年题库的题型地图2.1 六年题目按算法类别拆开看AoC 的题面包装很花有精灵、有工厂、有飞船但剥掉故事外壳底层算法类别相当集中。把 2015 到 2020 六年的题目按类别归一下大致是这么个分布类别典型年份与天数出现频率拿分难度字符串解析与模拟每年第 13 天极高低网格遍历与 BFS/DFS2016 第 13 天、2019 第 15 天高中动态规划2015 第 17 天、2018 第 12 天中中高图最短路2016 第 24 天、2019 第 18 天中高状态压缩与位运算2015 第 7 天、2020 第 14 天中高数学与数论2017 第 15 天、2020 第 25 天中中解释器与虚拟机2017 第 23 天、2019 第 23 天低但必考高这张表最该记住的不是频率是“难度爬升曲线”。前三天几乎全是解析加模拟第四天开始上网格第七天前后必出一道需要换数据结构的题第二周开始出现图论和 DP最后几天往往是一道综合题。备考时按这个曲线分配精力比按年份顺序刷效率高得多。字符串解析这块六年里没有一年缺席。2015 年第 1 天数括号方向2016 年第 1 天算最短路径2017 年第 1 天做循环求和2018 年第 1 天求频率累加2019 年第 1 天算燃料2020 年第 1 天找两数之和。这些题的共同点是输入格式固定、规则明确考的是读题细不细不是算法强不强。很多人在这类题上翻车不是不会写是漏了负号、漏了换行、漏了空行。网格类题目是第二个高频区。2016 年第 13 天走迷宫2019 年第 15 天在无限网格上找最近目标2020 年第 11 天做座位模拟。这类题的通用套路是先把输入读成二维数组定义方向数组写一个neighbors函数然后套 BFS 或模拟循环。方向数组写成[(0,1),(1,0),(0,-1),(-1,0)]还是加上对角线取决于题面说的是四邻接还是八邻接这一步看错后面全错。动态规划在 AoC 里不会明着写“请用 DP”而是包装成“有多少种组合”“最少需要多少容器”。2015 年第 17 天给一组容器容量问凑出 150 升有多少种组合这是典型的子集和计数用一维 DP 数组倒序更新即可。2018 年第 12 天是细胞自动机规则固定但状态会重复考的是发现循环节而不是硬模拟。这类题的答题思路是先写暴力版本验证小输入再观察状态空间最后决定是加记忆化还是找周期。图最短路是拉开差距的地方。2016 年第 24 天要求遍历多个目标点本质是旅行商问题的简化版先对每个目标点跑一遍 BFS 求两两距离再对目标点做全排列。2019 年第 18 天是带钥匙和门的迷宫状态里必须带上“已收集钥匙集合”用位掩码压缩。这类题面试官最想听的是你怎么定义状态状态空间多大为什么 BFS 在这个状态图上成立。2.2 每天两问的设计逻辑与分值意识AoC 每天两问不是随便拆的。第一问通常给一个小规模输入规则直白暴力就能过第二问要么把输入放大几个数量级要么加一层约束逼你从“能跑”升级到“跑得动”。这个设计和技术面试里的“先写暴力解再优化”完全同构。拿 2015 年第 6 天举例。第一问给一组开灯关灯切换指令网格是 1000×1000直接开二维数组模拟每条指令遍历矩形区域能过。第二问把“切换”改成“亮度加减”规则变了但结构没变还是矩形区域更新。这时候如果还用逐格循环1000×1000×300 条指令在 Python 里会明显变慢。更稳的写法是二维差分数组每次矩形更新只改四个角最后做一次前缀和还原。这个“从逐格到差分”的跳跃就是第二问真正想考的东西。分值意识在这里很重要。AoC 没有官方分数但社区有完成时间和星数。25 天共 50 星前 10 天拿满不算本事第 15 天之后每多拿一星含金量明显上升。备考时建议按“前 10 天求稳、中间 10 天求准、最后 5 天求懂”分配时间。前 10 天练的是读题和边界中间 10 天练的是选型最后 5 天练的是把复杂状态讲清楚。提示不要按年份从头刷到尾。按类别刷比如集中一周只做网格类把 2016 第 13 天、2019 第 15 天、2020 第 11 天放在一起做你会发现方向数组、边界判断、访问标记这三件事反复出现形成肌肉记忆。3. 高频真题演练五道代表性题目的答题思路3.1 2015 年第 1 天括号方向与“负一层”判定题面给一长串括号左括号上楼右括号下楼从第 0 层出发。第一问求最终楼层第二问求第一次到达负一层时的位置。第一问是纯计数s.count(() - s.count())一行解决。第二问要的是“第一次”所以必须顺序扫描维护当前楼层一旦小于 0 就返回下标加一。def first_basement(s: str) - int: floor 0 for i, ch in enumerate(s, start1): floor 1 if ch ( else -1 if floor 0: return i # 题目要求从 1 开始计数 return -1这段代码的关键在enumerate(s, start1)。AoC 的位置类问题经常从 1 开始计数而 Python 默认从 0 开始差一位就是错。另一个易错点是“第一次”三个字有人先算完整串再回头找逻辑上也能做但多扫一遍没必要。面试里被问到类似“第一次出现”的题先顺序扫描、命中即返回是最稳的答法。3.2 2016 年第 13 天网格 BFS 与方向数组题面给一个迷宫网格#是墙.是路要求从起点走到终点最少几步。这是最标准的 BFS 模板题。from collections import deque def bfs(grid, start, goal): rows, cols len(grid), len(grid[0]) dirs [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右下左上四邻接 q deque([(start, 0)]) seen {start} while q: (r, c), dist q.popleft() if (r, c) goal: return dist for dr, dc in dirs: nr, nc r dr, c dc if 0 nr rows and 0 nc cols \ and grid[nr][nc] ! # and (nr, nc) not in seen: seen.add((nr, nc)) q.append(((nr, nc), dist 1)) return -1seen集合在入队时就标记不要等出队再标记否则同一个点会被重复入队队列膨胀。方向数组的顺序不影响正确性但影响调试时打印出来的路径形状建议固定一个顺序。边界判断写成0 nr rows这种链式比较比nr 0 and nr rows短且不容易写反。如果题面是八邻接方向数组扩成八个其余不动。3.3 2018 年第 12 天细胞自动机与循环节发现题面给一组初始植物状态和生长规则每代按左右邻居决定下一代。第一问模拟 20 代第二问模拟 500 亿代。第一问直接模拟用字符串或集合表示活细胞位置。第二问 500 亿次循环不可能硬跑必须发现规律这类一维自动机在有限规则下很快进入稳定平移状态即每代图案不变、整体左移或右移固定格数。def simulate(state: set, rules: dict, generations: int) - int: seen {} offset 0 for gen in range(generations): key (frozenset(state), offset) if key in seen: cycle gen - seen[key] remaining (generations - gen) % cycle for _ in range(remaining): state, offset step(state, rules, offset) return sum(p offset for p in state) seen[key] gen state, offset step(state, rules, offset) return sum(p offset for p in state)这里用(状态, 偏移)做键是因为图案可能整体平移只比状态不比偏移会误判。发现循环后不用跑完剩余代数直接取模跳过去。这类题在面试里常被包装成“大数模拟怎么优化”答题时先说“先跑小规模观察是否出现周期”再说“用哈希表记录状态和代数”最后说“取模跳过剩余步数”三步讲完就是完整答案。3.4 2019 年第 18 天带钥匙迷宫与状态压缩题面是一个迷宫里面有门和对应颜色的钥匙拿到钥匙才能开门问收集全部钥匙的最短步数。这是 BFS 的变体难点在状态定义。普通 BFS 的状态是位置(r, c)这里不够因为同一个位置在不同钥匙持有情况下意义不同。状态要扩成(r, c, keys)keys是一个位掩码第 i 位表示第 i 把钥匙是否已拿到。def bfs_keys(grid, start): rows, cols len(grid), len(grid[0]) all_keys 0 for r in range(rows): for c in range(cols): if grid[r][c].islower(): all_keys | 1 (ord(grid[r][c]) - ord(a)) dirs [(0, 1), (1, 0), (0, -1), (-1, 0)] q deque([(start[0], start[1], 0, 0)]) # r, c, keys, dist seen {(start[0], start[1], 0)} while q: r, c, keys, dist q.popleft() if keys all_keys: return dist for dr, dc in dirs: nr, nc r dr, c dc if not (0 nr rows and 0 nc cols): continue ch grid[nr][nc] if ch #: continue if ch.isupper() and not (keys (ord(ch.lower()) - ord(a)) 1): continue # 没有对应钥匙门打不开 nkeys keys | (1 (ord(ch) - ord(a))) if ch.islower() else keys state (nr, nc, nkeys) if state not in seen: seen.add(state) q.append((nr, nc, nkeys, dist 1)) return -1状态空间大小是行 × 列 × 2^钥匙数钥匙数一般不超过 26但实际题目里往往只有几个所以完全可搜。面试里被问“状态怎么设计”答“位置加已收集资源集合集合用位掩码压缩”再补一句“状态数上界是格子数乘资源子集数”基本就到位了。3.5 2020 年第 14 天位掩码与浮空地址题面是一个简单的位操作虚拟机指令有“掩码置位”“掩码清零”“浮空位”。第一问按固定掩码写内存第二问掩码里的X表示该位可以是 0 也可以是 1一个地址会展开成多个地址。第一问直接按位与、按位或。第二问要对每个X位做枚举生成所有可能地址。def expand(addr: int, mask: str) - list: results [addr] for i, ch in enumerate(reversed(mask)): if ch 1: results [r | (1 i) for r in results] elif ch X: results [r | (1 i) for r in results] \ [r ~(1 i) for r in results] return results这段代码从低位往高位扫遇到1就置位遇到X就分裂成两份。注意~在 Python 里是无限位取反配合使用时结果正确但如果直接打印会看到负数别慌。枚举顺序不影响最终求和但影响调试可读性。这类题考的是对位运算的熟练度面试里常问“怎么枚举一个掩码的所有子集”标准写法是sub mask; while sub: ...; sub (sub - 1) mask和这里的展开逻辑是同一类思维。4. 易错点五类反复失分的题与答法纠正4.1 输入解析漏掉负号和空行错在哪直接split()或splitlines()后转整数遇到-3或空行就抛异常或算错。 为什么错AoC 的输入文件经常带前后空行、负数、混合分隔符默认解析假设太强。 怎么答对先strip()去首尾空白按行过滤空行再用int()转换遇到混合分隔符用正则re.findall(r-?\d, line)一次性抽出所有整数。面试里被问“怎么健壮地读输入”答“先规范化再解析不假设格式完美”。4.2 BFS 在出队时才标记访问错在哪seen.add写在popleft()之后导致同一个点被多次入队。 为什么错BFS 的正确性依赖“入队即标记”晚标记会让队列里堆积重复状态小图看不出大图直接超时或爆内存。 怎么答对入队前检查并标记出队只负责扩展。这个顺序在面试白板上写的时候要刻意念出来“我先标记再入队避免重复。”4.3 动态规划数组更新方向写反错在哪0/1 背包类问题里内层循环从小到大更新一维 DP 数组。 为什么错从小到大更新会让同一物品被重复使用变成完全背包答案偏大。 怎么答对0/1 背包内层倒序完全背包内层正序写之前先问自己“这个物品能不能重复选”。AoC 2015 第 17 天是组合计数每个容器只能用一次必须倒序。4.4 把“第一次出现”当成“最终结果”错在哪先算完整串再回头找位置或者用index()找但没处理找不到的情况。 为什么错题面要的是过程中第一次满足条件的时刻不是结束后再判断。 怎么答对顺序扫描维护当前状态命中条件立即返回。找不到时返回约定的哨兵值并在注释里写清楚。4.5 大数模拟不做周期检测直接硬跑错在哪第二问代数到了十亿级还写for _ in range(10**9)。 为什么错这类题的设计意图就是让你发现规律硬跑既过不了也不体现能力。 怎么答对先跑前几百代把每代状态存进字典发现重复就计算周期用取模跳过剩余步数。面试里讲这一步时重点说“我怎么判断进入了周期”而不是只贴代码。5. 答题节奏把六年题库拆成四周训练计划四周怎么排直接给一张可执行的表。前提是每天能拿出两到三小时周末多一点。周次训练重点具体题目验收标准第 1 周解析与模拟各年第 13 天不看题解独立写完输入解析零异常第 2 周网格与 BFS2016 第 13 天、2019 第 15 天、2020 第 11 天能默写 BFS 模板并解释标记时机第 3 周DP 与位运算2015 第 17 天、2018 第 12 天、2020 第 14 天能说清状态定义和更新方向第 4 周图论综合2016 第 24 天、2019 第 18 天能讲清状态空间大小和为什么可搜这张表的用法不是打卡是“卡住就停”。某道题卡超过四十分钟先去看别人的思路但只看思路不看代码回来自己重写。重写时把关键决策点用注释标出来比如“这里用位掩码因为钥匙数少”“这里倒序因为每个容器只能用一次”。这些注释就是你以后复习的索引。还有一个习惯值得强制养成每道题写完先拿题面给的小样例跑一遍再自己构造一个边界样例比如空输入、单元素、全墙迷宫、零容量容器。AoC 的题面通常会给一两个样例但样例往往覆盖不到边界自己补一个能挡掉大部分翻车。面试场景下这套题库的用法又不一样。面试官不会让你现场做完整道 AoC但会问“给你一个网格怎么找最短路”“状态里要带什么信息”“规模大了怎么优化”。这时候答题结构比代码更重要先说输入输出和约束再说选什么算法再说状态怎么定义最后说复杂度和边界。AoC 的题面描述长、约束藏在故事里正好练“从自然语言里抽约束”的能力。我自己的血泪经验是早年刷这套题总想一天做完一整年结果第三天卡住就整段放弃。后来改成按类别集中练每类只做三道做完写一段“这类题的通用骨架”反而记得牢。从那以后我每次遇到新题都强制先问三件事输入规模多大、状态里必须带什么、有没有周期或重复。这三问走完大部分题的方向就定了。希望帮到你。本文还有配套的精品资源点击获取
