PYTHON LESSON 095
考前 90 分钟冲刺训练
掌握“先易后难、客观题检查法、编程题抢分”的限时策略，会用格雷码公式与门牌号整除两大秒杀技。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- G(i) = i ^ (i >> 1) 格雷码公式秒杀
- while k >= 1: k //= 2 门牌号回溯
- bin(g)[2:].zfill(n) 二进制补零格式化
01 · 核心概念
限时答题策略与秒杀公式
限时答题策略与秒杀公式：开考先花 2 分钟通览全卷：客观题（选择+判断）目标 40 分钟内拿下，编程大题留 45 分钟，最后 5 分钟只检查、不改答案。遇到 3 分钟还没思路的客观题，先标记跳过——被一道题拖住整场，是最亏的失分方式。
GESP Python 6 级 · 格雷编码GESP Python 6 级 · 完全二叉树GESP Python 6 级 · 综合应用复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
G(i) = i ^ (i >> 1) 格雷码公式秒杀先准确读出这条写法的结构与作用。
while k >= 1: k //= 2 门牌号回溯换一组最小数据，手工推演一次结果。
bin(g)[2:].zfill(n) 二进制补零格式化再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 模拟冲刺热身：两个考场秒杀技 + 交卷检查口诀
# 秒杀技①：第 i 个 n 位格雷码不用递推，公式一步出答案
i = 5
n = 3
g = i ^ (i >> 1) # 异或：两位不同得 1；>> 1 右移一位
code = bin(g)[2:].zfill(n) # 转成二进制字符串，不足 n 位前面补 0
print("第", i, "个", n, "位格雷码是", code)
# 秒杀技②：完全二叉树里，从根到 k 号节点的路线反复整除 2 就出来
k = 13
route = []
while k >= 1:
route.append(str(k))
k = k // 2
route.reverse()
print("从根到 13 号节点的路线：" + " ".join(route))
# 交卷前最后 3 分钟，默诵检查口诀
print("交卷三查：递归出口、入队即标记、下标从几开始")第 5 个 3 位格雷码是 111 从根到 13 号节点的路线：1 3 6 13 交卷三查：递归出口、入队即标记、下标从几开始
秒杀技省下的时间，要全部投资给编程大题的检查环节。
04 · 逐步理解
每一步只解决一个问题
- 01
时间分配：先把卷子翻一遍
开考先花 2 分钟通览全卷：客观题（选择+判断）目标 40 分钟内拿下，编程大题留 45 分钟，最后 5 分钟只检查、不改答案。遇到 3 分钟还没思路的客观题，先标记跳过——被一道题拖住整场，是最亏的失分方式。
- 02
客观题检查法
树遍历题：在草稿纸上把树画出来再选，拒绝心算；格雷码题：用公式 G(i)=i^(i>>1) 抽查选项里相邻两项是否只差一位；完全二叉树题：默念“父 k//2、左 2k、右 2k+1”，把选项代进去验算。每个题型都有一件顺手的验证工具。
g = i ^ (i >> 1) - 03
编程题抢分策略
先写能拿部分分的朴素解：BFS 题哪怕只会统计可达格子数，也比空白强；确认跑通后再升级成完整解。输入输出格式严格照题目要求，多一个空格都可能判错。写完留 3 分钟，用题目给的样例重新跑一遍。
- 04
秒杀技①：格雷码公式
题目问“第 i 个 n 位格雷码”，千万别现场递推整个 2^n 长度的序列。i ^ (i >> 1) 一步出数值，bin 转字符串再 zfill 补零，一行搞定。递推法是 O(2^n)，公式法是 O(1)——这就是“记住结论”的分数价值。
code = bin(g)[2:].zfill(n) - 05
秒杀技②：门牌号整除链
“k 号节点的祖先是谁、从根到它怎么走”这类题，反复 k //= 2 收集编号再翻转即可，不用建任何树结构。判断 a 是不是 b 的祖先也同理：对 b 反复整除，看中途能否碰到 a。
while k >= 1: route.append(str(k)) k = k // 2 - 06
冲刺小练习
用题库 py-exam-l6-a1 和 py-exam-l6-a2 做一组限时训练：每题限 20 分钟，闹钟一响立刻停笔复盘。卡壳超过 5 分钟的地方就是你的补漏清单，回到对应主线课把那一节重学一遍。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，验证两个秒杀技的结果
- 2用公式法算出第 6 个 4 位格雷码
- 3给自己定一份 90 分钟时间分配表
- 4默写“交卷三查”口诀
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
计算机基础进制、整数表示与位运算从位权理解二、八、十六进制，准确使用补码模型、移位、掩码和 Python 大整数。＋
正式定义
b 进制数按位权 b⁰、b¹…表示数值。进制只是同一个整数的书写方式；位运算直接处理整数的二进制位。Python 整数精度只受可用内存限制，负数位运算按无限长二进制补码语义定义。
必须掌握
- bin/oct/hex 生成带前缀字符串，int(text, base) 按指定进制解析；0b、0o、0x 是整数字面量前缀。
- 手工转十进制用位权展开，十进制转其他进制可连续除基取余并逆序。
- & 取共同为 1 的位，| 合并置位，^ 标记不同位，~x 等于 -x-1。
- x << k 相当于 x * 2**k；对非负整数 x >> k 相当于 x // 2**k。
- 掩码可检测、设置、清除或翻转特定位；位编号通常从最低位 0 开始。
- 固定字长语言的溢出和 Python 大整数行为不同，题目必须明确字长和有无符号。
常见误区
- 把进制字符串当成不同数值类型
- 忘记位编号从 0 开始
- 照搬固定 32 位溢出结论到 Python
- 对负数右移套用无符号模型
适用边界
- 浮点数遵循 IEEE 754 的实现细节，不使用本章的普通整数进制模型直接推导。
- 字符编码把字符映射到整数，但编码知识与整数进制书写是两个不同层次。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
编码与文本字符串、转义、切片与格式化从不可变字符序列到检索、拆分、拼接、格式化和常用判断方法。＋
正式定义
str 是不可变的 Unicode 字符序列。下标访问单个字符，切片生成新字符串；任何看似“修改字符串”的方法都会返回新对象。
必须掌握
- 下标从 0 开始，负下标从末尾开始；切片 s[start:stop:step] 不包含 stop，step 不能为 0。
- 转义序列用于在字面量中表示换行、制表、引号、反斜杠或码点；原始字符串仍有末尾反斜杠限制。
- find 找不到返回 -1，index 找不到抛 ValueError；count 统计不重叠出现次数。
- split 把字符串拆成列表，join 用一个字符串连接可迭代对象中的字符串，strip 只删除两端字符。
- f-string 的格式说明可控制宽度、对齐、精度、进制和百分比；格式化不改变原值。
- isalpha/isdigit 等按 Unicode 定义，不只识别英文字母和 ASCII 数字。
常见误区
- 尝试 s[0] = 'A' 原地修改字符串
- 把 strip('ab') 误解为删除完整子串 'ab'
- find 返回 -1 后直接拿去当有效下标
- 把字节长度与字符长度混为一谈
适用边界
- 正则表达式不在低等级字符串必修范围，但复杂模式匹配时应使用 re，而不是堆叠大量 split/find。
- 面向用户的字符计数还可能涉及组合字符和字素簇，len 统计的是 Unicode 码点序列长度。
完成检查