01先把问题说具体
反转字符串、统计长度和查找字符看起来像数组操作,为什么同一段文字在不同语言中长度会不同?
02一步步得到方法
先决定你要操作哪种单位
字节是编码后的存储单位;Unicode 码点是字符编号;用户眼里一个可见字符还可能由多个码点组成,例如 e 与组合重音。Python str 通常按码点索引,UTF-8 字节串按字节索引,二者不能混为一谈。
本课的算法明确按码点工作。若要处理人类可见字符,应先按字素簇分段;按码点倒序可能拆开组合字符或 Emoji 序列。输入约定是算法正确性的一部分。
不可变字符串隐藏了什么工作
Python 字符串不能像列表一样原地赋值。a+b 要形成新字符串,切片也通常创建新对象。循环 s=s+piece 可能反复复制已经积累的前缀,最坏总工作量 1+2+…+n。
把片段先放入列表,最后 join 一次,可以先知道结果长度并按总字符数组合。这个方法减少重复复制,但列表和最终字符串仍需要空间,不能称为原地算法。
从双指针到规范化
判断回文时,不必先构造完整反转副本;可以比较两端码点并向内缩。若问题要求忽略大小写、空格或等价 Unicode 表示,应先明确规范化规则,再比较,不能默默删除信息。
03把一个小例子完全算清楚
按 Python 码点处理 s='A你🙂';另观察 'e\u0301'。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 编码前 | len('A你🙂')=3 | 三个 Unicode 码点 |
| UTF-8 编码 | 字节数 1+3+4=8 | 一个码点不一定对应一个字节 |
| 组合重音 | len('e\u0301')=2 | 视觉上常显示一个带重音字母 |
| 反转码点 | '🙂你A' | 本例各可见字符恰好都是单一码点 |
窄屏可左右滑动表格,阅读完整计算与理由。
长度取决于计数单位。本课代码适用于按码点定义的回文与拼接任务。
04为什么这个方法成立
- 双指针外部已经验证的对称位置相等。
- 若当前两个码点不同,整个字符串不可能为回文;相同时缩小到内部区间。
- 指针相遇后所有对称位置都已检查,空串和单码点串自然成立。
05把推导翻译成代码
Python · 可独立运行的教学实现
def palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def concatenate(parts):
return "".join(parts)逐个理解关键决定
s[left] != s[right]- 这里比较码点;不是比较 UTF-8 字节,也没有自动忽略大小写。
"".join(parts)- 先收集片段,再组合输出;结果长度是所有片段码点数之和。
06时间、空间与实现范围
长度 n 的回文检查最坏比较 floor(n/2) 对,时间 O(n),除输入外辅助空间 O(1)。
join 时间与总输出长度 L 及片段数相关,输出空间 O(L)。规范化、分段等预处理需要另算。
07改变条件,检查哪里会出错
把 UTF-8 字节倒序后解码
可能破坏多字节编码。先解码为文本,再按任务规定的码点或字素簇处理。
认为视觉上相同就一定逐码点相同
例如预组合 é 与 e+组合重音可有不同表示;需要时先采用一致的 Unicode 规范化。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
'上海自来水来自海上' 是码点回文吗?
需要一点提示
依次比较首尾。
查看解析与答案
是。每一对对称汉字相等。
'Aa' 在本课实现中返回什么?
需要一点提示
代码没有改写大小写。
查看解析与答案
False。若题意忽略大小写,需要显式 casefold 等规则,并重新界定预处理成本。
把 1000 个长度 1 的片段累加拼接,为什么可能比 join 慢?
需要一点提示
累计被复制的旧前缀。
查看解析与答案
普通模型中复制量可达 1+2+…+1000;join 以总长度为基准组装。不要把某个解释器的特定优化当成通用保证。