今天刷 LeetCode 的每日一题碰上 1784. 检查二进制字符串字段。题面不长给你一个二进制字符串 s判断由 1 组成的连续子串题目里叫“字段”是不是至多只能有一个。我第一眼看到“字段”这两个字脑子里先想起数据库表字段、JSON 字段稍一细看才发现这里的字段是英文 segment 的直译意思就是“连续的一段”。说白了这道题问的是一串只有 0 和 1 的字符串里1 的“聚集地”是不是只有一处。题目本身难度不高但非常适合算法入门者和准备面试的人练手因为它能同时带出字符串遍历、状态机、正则、边界条件这些基本功。接下来我把自己的完整复盘过程写下来从题目模型到五种解法、正确性证明再到我实际提交时踩过的坑一次讲清楚。1. 题目到底在考什么读懂“字段”这个模型1.1 原题描述与两个示例原题原文给你一个二进制字符串 s如果字符串中由 1 组成的最大连续子字符串字段不超过一个返回 true否则返回 false。输入输出解释s 1001false1 组成的连续块分别是下标 0 处的 1 和下标 3 处的 1一共有 2 块s 110true1 组成的连续块只有一个就是 11这里面有个很容易看懵的表述“最大连续子字符串”。官方说的是“由 1 组成的最大连续子字符串字段”其实“最大”在这里不是指长度最大而是指连续的、不能再向外扩展的完整块。更准确的说法应该是“连续段”或“连续区块”。一个字符串可以由若干个这样的 1 段组成中间用 0 隔开。我们只要统计这样的 1 段有几个超过一个就返回 false。1.2 别被名字劝退这里的“字段”不是数据库字段很多刚刷题的朋友看到“字段”两个字会习惯性地往数据库方向想我一开始也这样。实际上这个翻译来自英文的 segment它在字符串题目里的含义就是“由相同字符组成的连续片段”。你可以把字符串想象成一排灯字符 1 表示灯亮0 表示灯灭。字段就是一个连续的亮灯区间。题目要求的是整排灯里亮着的连续区间最多只能有一个。这个类比能帮助我们定位真正的判断目标要找的不是“1 的个数”而是“1 的连续块数”。“110”里面 1 的总数是 2但 1 的连续块是 1 个“101”里面 1 的总数也是 2但连续块是 2 个。一个字符串有 2 个 1 不一定非法有 2 块 1 才非法。我见过不少同学把这两者搞混后面的常见问题部分我会专门再讲。1.3 检查的本质字符串是否符合 010* 模式把问题再形式化一点一个二进制字符串里1 的连续段至多一个意味着所有出现在字符串里的 1 必须一个接一个紧挨在一起不能中间被 0 隔开。所以合法的字符串只有三种形态全是 0比如 0001 的段数是 00 前缀后面跟着一段连续的 1比如 001110 前缀、中间一段连续的 1、后面再跟 0 后缀比如 0011100。把这三类合并成一条正则表达式就是0*1*0*。也就是说这道题表面上是“检查二进制字符串字段”实质上是问这个字符串是不是 010* 这种形式。我从一开始就没急着写代码而是先把这个模型想透后面所有解法都是从这一个判断出发的。2. 五种实现方案从暴力扫描到状态机2.1 解法一线性扫描计数最直观的解法是遍历字符串数一数一共有几个 1 连续段。关键逻辑是什么时候算一个新段当当前位置是 1并且它左边不是 1也就是当前字符是段的开头时段数加一。第一段的开头还要考虑位置 0所以要加一个“i 0”的判断。class Solution: def checkOnesSegment(self, s: str) - bool: cnt 0 n len(s) for i in range(n): if s[i] 1 and (i 0 or s[i - 1] 0): cnt 1 if cnt 1: return False return True时间复杂度 O(n)空间复杂度 O(1)。这个写法最贴近问题定义几乎不需要额外知识是面试时最保险的解法。有一个容易被忽视的点当整个字符串都是 0 时cnt 始终是 00 小于等于 1返回 true这是符合题意还是不符合题意要搞清楚题目说的是“由 1 组成的字段至多一个”0 个字段当然至多一个所以返回 true。我见过有人在这里写了cnt 0 or cnt 1之类的冗余判断其实没必要。2.2 解法二split 切分与长度判断Python 选手可以用 split 一行把问题解决用字符 0 把字符串切开剩下的非空片段就是 1 连续段。然后数一下非空片段的数量是否不超过 1。class Solution: def checkOnesSegment(self, s: str) - bool: return len([part for part in s.split(0) if part]) 1这个解法很 Pythonic但它不像表面看起来那么“取巧”。“101”被切出来是两个片段 1 和 1长度是 2返回 false“0110”被切出来是空串、11、空串过滤空串后只有一个片段返回 true。本质上它做了和线性扫描一样的事情只是把“找连续段”的活交给了 split 的底层实现。要注意的是 split 会额外创建一个列表在 n 很大的时候内存开销比计数法高不过这道题 n 最大只有 100完全不用担心。2.3 解法三正则全匹配如果我们已经知道合法字符串属于 010*那最直接的实现就是写一条正则用 fullmatch 判断整个字符串完全匹配import re class Solution: def checkOnesSegment(self, s: str) - bool: return re.fullmatch(r0*1*0*, s) is not None正则表达式0*1*0*表示任意多个 0然后任意多个 1再然后任意多个 0。注意这里每一步都是“任意多个”所以空字符串、全 0、全 1 都能匹配。这里最容易翻车的点是必须使用 fullmatch完全匹配不能使用 search 或 match后面踩坑部分我会专门展开。正则解法不是我平时会优先提交的答案但在讲解思路时非常好用因为它把题目模型直接翻译成了规则。Java 里对应的写法是s.matches(0*1*0*)C 里可以用std::regex_match(s, std::regex(0*1*0*))思路完全一样。2.4 解法四双指针扫过整个串双指针解法把“010*”拆成三个连续的阶段先跳过前导 0再跳过一段连续的 1最后检查剩余的字符里还有没有 1。class Solution: def checkOnesSegment(self, s: str) - bool: n len(s) i 0 # 第一阶段跳过前导 0 while i n and s[i] 0: i 1 # 如果已经结束说明全是 0 if i n: return True # 第二阶段跳过唯一的一个 1 连续段 while i n and s[i] 1: i 1 # 第三阶段剩下的必须是 0一旦出现 1 就违规 while i n: if s[i] 1: return False i 1 return True这个写法的思路比计数法更接近“模型”它不是在数段数而是直接验证字符串的形状是不是 010*。如果在跳完那一段 1 之后还能碰到 1说明 1 被 0 分成了两段“1001”在这个逻辑下会在第三阶段遇到下标 3 的 1直接返回 false。双指针写法的时间空间复杂度都是 O(n)/O(1)而且不容易踩到负数索引的坑我推荐没把握的同学优先用这种。2.5 解法五三状态自动机从状态机的角度看检查过程可以分成三个状态状态 0还没有进入 1 字段处于前导 0 区域状态 1正在 1 字段内部状态 2已经离开 1 字段处于后缀 0 区域。每读一个字符根据当前状态做迁移。如果已经进入状态 2 却又碰到 1说明 1 字段不止一个直接返回 false。class Solution: def checkOnesSegment(self, s: str) - bool: state 0 for ch in s: if ch 1: if state 2: return False state 1 else: # ch 0 if state 1: state 2 return True状态机解法看起来比计数法复杂但它把“合法模式”的形式化表达推向极致状态 0 → 状态 1 → 状态 2 的路径清晰对应 010* 的识别过程。很多人觉得状态机是高大上的东西其实它的核心就一句话记住当前处于哪个阶段根据新输入决定下一步怎么走。这个思维在解析 HTTP 头、JSON、CSV 等文本格式时非常常用后面第五章我会再展开。2.6 五种方案横向对比方案核心思路时间复杂度空间复杂度代码量线性计数统计 1 连续段个数O(n)O(1)6 行split 切分按 0 切分后数非空段O(n)O(n)1 行正则匹配判断是否匹配 010*O(n)O(1)1 行双指针分阶段验证字符串形状O(n)O(1)10 行状态机用三个状态模拟合法轨迹O(n)O(1)8 行真正面试时我一般会先讲计数法因为它的语义最贴近题目、几乎不会被追问如果面试官问“还有没有更优雅的写法”再补充正则或 split。这五种方案的差异其实都在表达层面底层判断逻辑完全等价。3. 正确性与边界为什么这些解法都成立3.1 从“字段数”到“010*”的等价性证明不少读者可能觉得“代码 AC 了证明无所谓”。但简单题正是练证明的好机会这里我用几句话说明白为什么这些解法都对。先证明“合法性 010*”如果字符串里 1 的连续段至多一个那么所有 1 一定集中在从左到右的某个连续区间 [l, r] 内。区间之前的字符不可能是 1否则它要么和 [l, r] 连在一起那区间就不是从 l 开始要么自成一段那字段就至少两个都会矛盾区间之后的字符同理也不可能是 1。因此字符串只能是若干个 0、再一段连续的 1、再若干个 0即 010*。再证明“010* 合法性”如果字符串满足 010*中间那段 1 如果为空1 的字段数是 0如果不为空因为 0 前缀和 0 后缀里都没有 1整个字符串里就只有这一段 1字段数恰好为 1。两边等价所以检查“字段是否至多一个”和检查“字符串是否属于 010*”是一回事。后面我在状态机、正则、双指针里的每一步本质上都是对这个正则语言的识别所以它们的结果必然一致。证明没有必要写得非常数学化能自洽就行但心里有这个等价关系写任何解法都不会跑偏。3.2 边界情况速查表我每次提交前都会先跑一组手写的边界样例。针对这道题我整理了一张表覆盖了所有容易翻车的形态输入预期结果原因0true1 字段数为 00 ≤ 11true只有一个 1 字段00true没有 1 字段11true单个 1 字段 1101true前导 0 单个 1 字段10true单个 1 字段 后缀 0101false1 被 0 分隔成两段1001false同上0110true1 字段是连续的 1111011false11 和 11 是两段001100true前后缀都有 0中间只有一个 11这张表几乎覆盖了所有边界单字符、全 0、全 1、前导 0、后缀 0、字段被分隔、字段在中间。写完代码后顺手在脑内跑一遍这些样例基本可以保证不翻车。如果是在编辑器里调试直接把表格里的输入做成一个列表循环打印结果就行。3.3 复杂度、内存与语言特性细节虽然 n 很小让这道题毫无性能压力但养成关注复杂度习惯很重要。计数法、双指针、状态机都是严格 O(n) 时间、O(1) 额外空间而且只扫描一遍字符串这是最优复杂度。split 的时间是 O(n)但因为要创建列表存储切分结果额外空间是 O(n)正则匹配在 Python 的 re 底层通常也是线性时间但正则引擎匹配特殊模式时可能有一定常数开销。如果将来遇到长度达到百万级的大字符串我建议优先用计数法或双指针尽量避开 split 和正则。刷题时可以把这道题当作复杂度分析的练习即便 n 很小也明确说出每种做法的复杂度这个习惯在面试里很加分。4. 我实际提交时踩过的坑与排查记录4.1 算错了对象统计成 1 的总个数这个坑是初学者最容易踩的。有人一看题目“由 1 组成的字段不超过一个”就写成了s.count(1) 1。这个写法对 110 会返回 false但正确答案是 true因为 110 里有两个 1可是它们连在一起构成的是一个字段。如果按总数判断等于把“字段数”和“1 的个数”混为一谈。这种错误不是单纯粗心而是没有先建立“连续段”的模型。解决问题的方式就是先理解字段 连续块再动手编码而不是看到二进制字符串就直接统计字符数量。4.2 被子串迷惑“01” 存在不代表非法还有一个很自然的想法既然合法的模式是 010*那只要没有 “01” 后面再接 1 的情况就行于是有人写return 01 not in s or ...。这里有个陷阱字符串 0110 是合法输入它却包含子串 01下标 0 到 1。所以直接判断01 in s会误判。正确检查“是否出现新的 1 字段”要看的是“离开 1 字段后再进入 1 字段”也就是正则里的101模式而不是简单看有没有 01。这也是为什么我在前面推荐先想清楚等价模型再写代码——被单个子串迷惑多半是因为没有模型。4.3 Python 负数索引的隐性坑Python 里s[-1]能取到最后一个字符这个特性在写“当前字符的前一个字符”时特别容易埋雷。有人把计数法的判断写成if s[i] 1 and s[i - 1] 0 and i 0:这个顺序表面看着没问题但 i 为 0 时s[-1]也能执行取到的是字符串最后一个字符不会报错。比如 s 001i 0 时执行s[-1] 0发现最后一个字符是 1条件为 false于是漏掉了对首字符的判断最终返回错误答案。在 Java 或 C 里这么写会直接越界崩溃至少能暴露问题Python 不崩反而更难排查。我的经验是涉及s[i-1]的判断一定要把i 0放在最前面利用短路求值避免计算负数索引或者干脆用双指针/状态机这类不依赖前一个字符的写法。4.4 正则忘写 fullmatchAC 变 WA用正则时如果写成re.search(r0*1*0*, s)结果会恒为真。原因是 search 会在字符串里寻找任意匹配的子串而0*1*0*因为每一部分都能接受空串会在任意位置以空字符串身份匹配成功。必须用re.fullmatch或者用re.match加上$锚点re.match(r0*1*0*$, s)。这道题因为名字带“检查”很多人第一反应就是正则匹配结果 30 秒写完却怎么都 AC 不了。这个坑很隐蔽我建议用正则解字符串匹配题时心里默认第一选择是 fullmatch 或者明确带^、$锚点除非题目真的要求子串匹配。4.5 顺手收藏的一个取巧写法strip(0)最后分享一个我后来才发现的取巧写法代码短到惊人class Solution: def checkOnesSegment(self, s: str) - bool: return 0 not in s.strip(0)思路是先去掉字符串首尾的 0如果剩下的部分还有 0说明字符串中间还夹着 0那 1 字段一定不止一个如果剩下的部分没有 0说明去掉首尾后只剩下连续的 1或者全 0 串去掉后为空合法。这个写法和我前面五种解法在逻辑上完全一致只是把“前缀 0 和后缀 0”这个观察单独提了出来。我一般不会拿这种一行版本去面试因为它解释起来反而需要多绕一步但作为日常刷题的趣味解法可以收藏。5. 从一道简单题说开去段模型与状态机的工程价值5.1 连续段思想在同类题中的复现“统计连续段”是算法题里一个高频思考模式跟这道题强相关的题我能立刻想起一堆485 题求最大连续 1 的个数1446 题求连续相同字符的最大长度1759 题统计同构子字符串数量696 题要求数出所有形如 0/1 交替的二进制子串443 题做字符串压缩时要按段处理。它们共同的核心都是在遍历过程中识别“一个段的开始”和“一个段的结束”。比如 485 题你同样要维护“当前是不是在 1 段里”这个状态一遇到 0 就结算当前段的长度。练好 1784 这道题等于给这整类题打了一个地基。我刷题时有个习惯遇到一道简单但思路清晰的题就主动想想它跟哪些题是同一个模型然后放到一起复习远比单道题重复十遍效果好。5.2 状态机不只是面试题也是解析器的底层状态机解法在这道题里看起来有些“杀鸡用牛刀”但它背后是一个非常重要的工程思想任何文本解析都可以建模成“当前状态 当前输入 → 下一状态”。举个例子解析 HTTP 响应头时你可能要区分当前行是状态行、头部字段还是空行分隔符写出的代码本质上就是状态机写 JSON 的 tokenizer 时你要区分当前处于字符串、数字还是对象结构的什么位置同样要靠状态迁移。我在实际工作中写过一个简单的日志解析器专门从每一行日志里提取等级和时间戳最初的版本用大量 if 嵌套后来重构成状态机代码清晰度和可维护性都上了一个台阶。回到这道题如果你能体会到“0 前缀 → 1 段 → 0 后缀”三个状态以后再面对更复杂的格式识别思路就会顺很多。5.3 面试时怎么把这道题讲出层次这道题如果出现在面试里千万不要上来就甩一个一行 Python。我建议按这个顺序讲先复述题意澄清“字段”就是连续段然后给出计数法说明“遇到 1 且前一位不是 1 时计数加一”接着主动补充一句“这个判断等价于检查字符串是否符合 010*”再随手给出双指针或状态机的版本最后把全 0、单字符、101、1001 这几个样例快速过一遍。这样不到两分钟就能展示出你会建模型、会证明、会做边界分析。面试官大概率会追问一句“还有更简单的实现吗”这时再抛出 split 或正则效果是最好的。拿我自己来说这道题我前后用五种方法写过隔了两个月再回头看印象最深的反而不是 AC 本身而是那个 010* 的模型。把简单题吃透比赶着刷三遍难题更值得。