📑 本页目录（点开跳转）
08 · 字符串与输入：脏输入也要有边界
⏱ 10 分钟 ｜ atoi、回文、翻转单词、字符流
🎯 一句话
字符串题的本质常常是一个小状态机：当前读到哪里、已经确认了什么、下一类字符还允不允许出现。
🧩 题 1：把字符串转换成整数（atoi）
顺序固定：跳空格 → 读正负号 → 连续读数字 → 处理溢出。任何一步不符合规则就停止，而不是“尽量猜”。
def my_atoi(text):
index, sign, value = 0, 1, 0
while index < len(text) and text[index].isspace():
index += 1
if index < len(text) and text[index] in '+-':
sign = -1 if text[index] == '-' else 1
index += 1
while index < len(text) and text[index].isdigit():
value = value * 10 + int(text[index])
index += 1
value *= sign
return max(-(2**31), min(2**31 - 1, value))
assert my_atoi(' -42x') == -42
assert my_atoi('words and 9') == 0
assert my_atoi('91283472332') == 2**31 - 1
🧩 题 2：最长不含重复字符的子字符串
窗口的左边界只向右走。每次遇到重复字符，就把左边界跳到它上一次出现位置的后一格。
def longest_unique(text):
last_seen, left, best = {}, 0, 0
for right, char in enumerate(text):
if char in last_seen and last_seen[char] >= left:
left = last_seen[char] + 1
last_seen[char] = right
best = max(best, right - left + 1)
return best
assert longest_unique('abcabcbb') == 3
assert longest_unique('bbbbb') == 1
🧩 题 3：字符流中第一个不重复的字符
一边读一边维护两个事实：每个字符出现次数，以及第一次出现的顺序。队首若已经重复就淘汰。
from collections import Counter, deque
class FirstUniqueStream:
def __init__(self):
self.counts, self.queue = Counter(), deque()
def insert(self, char):
self.counts[char] += 1
self.queue.append(char)
while self.queue and self.counts[self.queue[0]] > 1:
self.queue.popleft()
def first_unique(self):
return self.queue[0] if self.queue else '#'
stream = FirstUniqueStream()
for char in 'google':
stream.insert(char)
assert stream.first_unique() == 'l'
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| Python 会咬你的地方 09 · 容器、哈希与顺序 | ⭐ 题 3 靠的是 Counter + deque 和「第一次出现的顺序」。那一章讲这批容器各自保不保序：dict 从 3.7 起保证插入序，set 从来不保证，而且它的实际顺序每次进程启动都会变 |
🛑 可以停在这里
看到字符串解析题，先列出合法阶段，而不是先写一堆 if。阶段明确，边界自然会出现。
✅ 检查点
最长无重复子串为什么左边界从不回退？
👀 看答案
右边界已经向右扩展；回退左边界只会把已知会冲突的字符重新放回窗口，既无帮助又会重复计算。
⚡ 走神救援
- atoi：空格、符号、数字、溢出四个阶段。
- 滑动窗口：左右边界都只向右，不回头。
- 字符流：次数负责判断重复，队列负责保留先后。
下一步： 回到 00 · 怎么刷代码题，挑一题遮住代码重写。
继续： 附录A · 速查