前几天刷 LeetCode 的时候有个朋友丢了一个链接过来1784Check if Binary String Has at Most One Segment of Ones。他说这题看着简单但提交了两次都因为边界挂了。我打开题目看了一遍确实是个典型的“一看就会、一写就错”的字符串判断题。题目给一个二进制字符串让你判断所有连续出现的 1 是不是都挤在同一个小团队里——说得正式点就是字符串里的连续 1 字段数量是否至多为 1。这篇题解会从题意拆解讲到多种解法、复杂度分析、边界用例再到面试时可以怎么组织表达最后把我自己踩过的坑一起列出来。1. 题目到底在说什么拆掉包装看本质1.1 先读题输入、输出与判定规则先别急着写代码把题面读清楚。题目给你一个二进制字符串s并且特别强调这个字符串没有前导零without leading zeros。你需要返回true或false判断的是字符串里所有由1组成的连续片段是不是最多只有一段。这里的“一段连续 1”意思是一串相邻的1它的左右两边要么是字符串边界要么是0。举个例子111是一段连续的 101110中间也有一段连续 1而101就是两段连续 1因为中间被一个0隔开了。题目给“无前导零”这个条件非常关键。它意味着合法的输入要么以1开头要么就是极端的空串不过 LeetCode 原题的约束是1 s.length所以正常测试用例里没有空串。很多题解之所以能写出非常短的代码全靠这个前置条件。这道题的难度是 Easy但它不是那种无脑遍历就能满分通过的题重点在于你能不能把“连续 1 字段检查”这个条件转化成一段既简洁又不会踩坑的逻辑。先想清楚我们到底要判断什么1.2 用例子说话手动走一遍判定过程先拿几个典型输入练练手输入连续1字段数量结果11 段true101 段true1101 段true1012 段false10012 段false1111 段true00 段true至多一段0段也算0000 段true注意0和000这两种输入虽然不符合题目的“无前导零”约束但如果我们要写一个通用性更强的解法也应该能正确处理没有1连续 1 字段数量是 00 当然不超过 1所以返回true。手动判断过程就一句话从左往右扫数一数“从 0 变 1”的次数。每出现一次这样的切换就说明开启了一个新的连续 1 字段。如果这个次数大于 1就返回false。1.3 本质转化问题等价于“1 的段数不超过 1”把“连续 1 字段检查”翻译成更数学一点的说法统计字符串中连续 1 的段数。段数 0 或 1都满足条件段数 ≥ 2不满足。这一步转化是整道题的核心。很多人在 LeetCode 题解里看到的所谓“简单解法”本质上都是在用各种技巧统计段数或者利用题目条件绕开统计。比如有人用s.find(1)和s.rfind(1)有人用正则表达式有人直接查子串01。它们背后的逻辑其实都一样想办法判断字符串里有没有出现第二次“从 0 到 1”的切换。只要抓住“段数”这个核心后面所有解法都能串起来。2. 多种解法对比从直觉到最优2.1 解法一段数计数最稳也最通用最直接的思路就是遍历字符串统计连续 1 的段数。用一个变量cnt记录已经出现的段数再用一个变量prev记录前一个字符。每当当前字符是1且前一个字符是0或者当前字符是开头的1时就说明新开了一段cnt加 1。def check_ones_segment(s: str) - bool: cnt 0 prev 0 for ch in s: if ch 1 and prev 0: cnt 1 if cnt 1: return False prev ch return True这段代码的巧妙之处在于把prev初始化成0这样字符串第一个字符如果是1也会被正确识别为新的一段。如果字符串是空串循环不执行直接返回True语义也正确。这种解法不依赖“无前导零”的题目约束哪怕给你一个00100它也能正确返回true。所以它是最通用、最不容易出错的版本。2.2 解法二首尾夹逼检查中间有没有 0第二种思路完全围绕定义展开如果所有 1 都在同一段那么从第一个 1 到最后一个 1 之间不能出现 0。因此可以找到s中第一个1的位置left和最后一个1的位置right然后检查s[left:right1]这个子串里有没有0。def check_ones_segment(s: str) - bool: left s.find(1) if left -1: return True right s.rfind(1) return 0 not in s[left:right 1]这个解法胜在直观几乎不用推导。但它有一个必须处理的边界字符串里可能一个1都没有。此时left和right都是-1如果直接切片会得到一些奇怪的结果所以要先单独处理。从时间上来说find和rfind各自扫一遍理论上最坏是两次遍历但依然是 O(n)。空间上只用常数变量O(1)。2.3 解法三利用“无前导零”的 Trick查子串 “01”这道题在 LeetCode 上最火的解法可能是这个def check_ones_segment(s: str) - bool: return 01 not in s乍一看很神奇为什么会成立因为题目保证s没有前导零所以正常输入要么是空串要么以1开头。如果字符串里出现子串01意味着在某个0之后又出现了一个1。由于字符串是从1开始的前面已经有一段连续的 1 了后面的这个1肯定属于新的一段于是至少有两段连续 1直接返回false。反过来如果字符串里完全没有01这个子串那么所有 0 只能出现在所有 1 的后面也就是字符串整体呈1...10...0的形状所有 1 自然是连续的一段返回true。这个解法写起来只有一行但有一个致命前提题目必须保证没有前导零。如果输入可能是01这个解法会错误地返回false。因为01本身包含子串01但实际上它只有一段连续的 1就是末尾那个 1应该返回true。所以在面试或写题解时如果要用这个 Trick一定要把前提条件说清楚。2.4 解法四正则表达式一行收工但要谨慎除了手动遍历还可以用正则表达式来匹配字符串的形状。既然要判断“最多只有一段连续 1”那字符串的形态只能是任意数量的 0 开头中间最多一段连续的 1再接任意数量的 0。对应的正则就是^0*1*0*$。import re def check_ones_segment(s: str) - bool: return re.fullmatch(r0*1*0*, s) is not None如果题目保留“无前导零”的条件可以把正则简化成^1*0*$因为字符串必须以 1 开头。import re def check_ones_segment(s: str) - bool: return re.fullmatch(r1*0*, s) is not None正则表达式的优点是语义清晰一眼就能看出在匹配什么形状。缺点是很多人在面试场合下不敢写正则怕被追问底层实现另外不同语言的正则引擎对fullmatch的支持也不一致容易踩坑。我的建议是可以作为补充思路提一嘴但主答案不要依赖正则。2.5 复杂度与选型建议解法时间复杂度空间复杂度是否依赖“无前导零”推荐场景段数计数O(n)O(1)否最通用面试首选首尾夹逼O(n)O(1)否逻辑直观适合讲解查子串 01O(n)O(1)是代码最短但需说明前提正则表达式O(n)O(1)视写法而定适合作为思路补充如果让我给一个明确的建议在 LeetCode 上提交我通常写段数计数版本因为它不依赖题目约束边界也干净。如果是在面试里我会先讲段数计数然后提一句“如果利用无前导零的条件还能简写成检查01是否出现”既能展示代码能力也能展示对题目条件的敏感度。3. 核心实现拆解写出健壮的代码3.1 逐行拆解段数计数版把段数计数版本再拿出来细看def check_ones_segment(s: str) - bool: cnt 0 prev 0 for ch in s: if ch 1 and prev 0: cnt 1 if cnt 1: return False prev ch return True第一行cnt 0用来记录已经看到的连续 1 段数。第二行prev 0是虚拟的前一个字符它的作用是把字符串的起始边界当成一个 0。这样处理之后循环里就不需要单独判断i 0的情况。循环内部的判断条件是ch 1 and prev 0翻译成人话就是当前位是 1而且前一位不是 1。这就说明我们正站在一段连续 1 的入口处。每遇到一次这样的入口cnt加 1。一旦cnt超过 1立即返回false。这里可以直接返回因为后面无论再出现什么都不可能把已经存在的两段 1 合并成一段。循环末尾的prev ch是标准的滚动更新把当前字符变成下一轮判断中的“前一个字符”。这段代码我刷题时经常当作模板用因为它可以轻松扩展成“统计连续 1 段数”的通用工具只要把return True换成return cnt就能得到段数。这种从判断题扩展到计算题的思路在面试里很加分。3.2 双指针版本的隐藏坑首尾夹逼版本看起来简单但有一个藏在细节里的坑字符串里可能没有1。left s.find(1) if left -1: return True right s.rfind(1) return 0 not in s[left:right 1]如果不加left -1的判断假设s 000left和right都是-1切片s[-1:0]会得到一个你意想不到的子串结果完全不可控。加了这个判断之后全 0 串直接返回true因为 0 段 1 是满足“至多一段”的。还有人会问为什么不直接用len(s) 1这类判断因为我们要的不是字符串长度而是有没有1。用find的返回值来判断是最稳妥的。如果你用的是 JavaScript写法类似function checkOnesSegment(s) { const left s.indexOf(1); if (left -1) return true; const right s.lastIndexOf(1); return !s.slice(left, right 1).includes(0); }JavaScript 的slice和 Python 的切片一样都是左闭右开所以right 1不能漏。3.3 边界用例全集边界用例是这道题真正的考点。我把自己测试时用到的用例整理成一个全集输入期望结果说明true空串0 段 1非原题约束但通用解法应支持0true0 段 11true只有一段长度为 100true0 段 111true一段连续 110true一段 1 后接 01100true一段 1 后接多个 00110true前导 0 一段 1 后置 0通用解法应返回 true101false两段 1中间隔一个 01001false两段 1中间隔两个 01010false两段 1后面还有 001010false两段 1且以 0 开头这里特别说一下0110。如果直接用查子串01的 Trick0110包含01会返回false但正确答案应该是true。原因就是0110有前导零不满足题目的“无前导零”约束。所以一律建议用不依赖该约束的段数计数法来测试所有边界。3.4 为什么正确从反证法看算法可靠性有人可能会想段数计数法真的够吗会不会漏掉某种情况我们来做一个简单的反证。假设字符串里有至少两段连续 1那么必然存在一个位置使我们在遍历时第一次从 0 切换到 1。这是第一段。既然最终至少有两段那么在第二段开始的位置一定又是一个从 0 切换到 1 的过程。遍历算法会把这次切换记录下来cnt变为 2于是返回false。反过来如果算法返回false说明在遍历过程中至少遇到了两次“从 0 变 1”的切换。每一次切换都代表进入一段新的连续 1所以至少有两段。这与算法的判断形成严格的双向等价。这种“一次遍历捕捉状态切换”的思路比单纯记住结论要可靠得多。面试时能把这一段推理讲清楚比背代码更有说服力。4. 这题真正在考什么算法思维与面试表达4.1 不变量思维贯穿整个扫描过程段数计数法里有一个隐藏的不变量在一次遍历过程中cnt表示“到目前为止已经开始的连续 1 段数”。这个值只会增加不会减少因为一段 1 一旦结束之后不可能再变成一段新的 1 但让段数减少。理解了这个不变量你就能自然解释为什么可以提前返回一旦cnt 1不管后面怎么走都不可能回到合法状态。这就像你数楼层已经数到 3 楼了就不可能突然变成 1 楼。很多字符串判断题比如验证括号、检查重复字符、判断数字字符串本质上都是在维护某个不变量。1784 这道题把不变量思维压缩在一个很小的例子里特别适合用来学习和讲解。4.2 状态机视角把遍历看成状态迁移段数计数法还可以升级成更通用的状态机写法。我们维护三种状态状态 0还没见过任何 1。状态 1正处于一段连续 1 中。状态 2这段 1 已经结束或者整串已经扫描完。遍历开始时状态为 0。遇到 1从状态 0 切到状态 1或者从状态 2 切到状态 1。后者意味着出现新的一段 1直接判非法。遇到 0如果当前在状态 1切换到状态 2如果在状态 0 或状态 2状态不变。状态机的优势在于它把“什么条件下非法”变得非常明确只有在状态 2 时又看到 1才非法。把逻辑固化下来之后代码的可读性和可测试性都会提升遇到复杂一点的变体题也能快速套用。4.3 横向对比和“最长连续 1”类题目怎么区分LeetCode 上有不少和连续 1 相关的题比如 485 题“最大连续 1 的个数”1004 题“最大连续 1 的个数 III”。它们和 1784 的区别要搞清楚。485 题问的是“最长的连续 1 有多长”这是一个最优化问题需要统计所有连续 1 段并取最大值。1784 问的是“是否最多只有一段连续 1”这是一个判定性问题只要发现第二段就可以提前退出不需要关心每段有多长。1004 题更复杂一点它允许你把最多 K 个 0 翻转成 1然后求最长的连续 1 长度。这种题要用滑动窗口窗口里维护 0 的个数。表面上看都是字符串和连续 1但解法思路完全不同。所以刷题不能只看关键词还要分清问题类型是判定性、计数、最值还是可修改条件下的最值。1784 是个很好的分水岭能帮你建立这种分类意识。4.4 延伸对比和二分答案类题目的思维差异最近周赛 430 前后我在地铁上刷到不少题解发现很多人会把各类判定问题统一到一个框架里先写一个check函数再去主流程里反复调用。比如 LeetCode 875 题“爱吃香蕉的狒狒”不少人把它归在热题 100 的第 73 位核心就是写一个“在给定速度下能否吃完”的check函数然后对速度做二分。1784 和这种二分答案题有什么联系它不是二分但它同样要求你把题意抽象成一个可复用的判断规则。段数计数里的cnt本质上就是一个“判定器”输入一个字符更新段数超过阈值就判负。如果你能把 1784 写成这种风格那么在面对更复杂的二分判定题时思路迁移会非常顺畅。所以别因为这道题是 Easy 就草草跳过把它当成训练“条件翻译”能力的小样本价值比想象中大。5. 实战中的坑与排查实录5.1 坑一把“全 1”当作判断条件我第一次写这道题时脑子里冒出来的想法是如果字符串里全是 1那就一段如果字符串里 0 和 1 混在一起就看看是不是1...0...的形状。结果写出来的代码是if 0 not in s: return True这个判断只覆盖了全 1 的情况漏掉了10、110、1000这类合法输入。它们不是全 1但确实只有一段连续 1。很快我就意识到不能拿“字符串里有没有 0”当判断依据而要看“0 是否插在 1 段中间”。这个坑的教训是不要用直观感觉替代形式化定义。回到定义把所有合法形态列出来再写代码。5.2 坑二用了“01”检查但忘记题目约束我在另一版提交里写了return 01 not in s自测101和110都过了结果一多想发现01本身就会判错。如果题目没有“无前导零”这个条件这个一行版本就是有漏洞的。后来我在代码注释里专门写了一行此解法依赖题目的无前导零约束。面试时也可以主动说如果不作这个假设我会改回段数计数版。这种“明确指出代码适用前提”的表达方式在面试里非常加分。5.3 坑三find 和 rfind 遇到 -1 的情况前面提过的全 0 串问题实操中经常遇到。还有一个类似的错误是有人会写if s.count(1) 0: return True然后再去找左右边界逻辑上没错但多扫了一遍。既然find返回-1本身就说明没有 1不如直接复用这个返回值。我用的是一个统一写法把find的结果存在变量里先判-1再做后续操作。这样既避免了重复扫描也避免了切片边界错乱。5.4 坑四正则表达式在笔试环境里的兼容性有次我在本地用 Python 写re.fullmatch(r0*1*0*, s)跑得很欢结果换到一个只有老版本 Python 的在线环境发现re.fullmatch是 Python 3.4 才引入的。虽然现在大部分环境都支持但在面试白板上手写正则然后被追问“这个正则的时间复杂度是多少”就比较尴尬。正则引擎对*的处理多数是线性的但你很难在三言两语里解释清楚。所以我现在的习惯是正则只作为口头补充不当作最终提交版本。5.5 快速排查模板如果你在调试这类字符串判断题时找不到 bug可以按下面的顺序排查把题目约束写出来特别是“无前导零”“非空”这类容易被忽略的前置条件。列出所有边界输入至少包含空串、全 0、全 1、单个 1、单 0、前后 0、交替出现等情况。在遍历循环里打印关键变量比如cnt和prev手动模拟一遍状态切换。拿你的解法去套0110这种带前导零的用例确认解法是否依赖题目约束。这个模板不只适用于 1784大部分字符串判断类问题都能套用。6. 写码之后我给自己反复强调的三条经验6.1 Easy 题考的是条件翻译不是算法复杂度1784 没有复杂的算法时间复杂度和空间复杂度都一眼见底。它真正考察的是你能不能把一个自然语言描述的条件精确地翻译成代码逻辑。面试官想看的也不是你会不会背“查 01”这个 Trick而是你能不能讲清楚为什么这样判断是正确的。6.2 边界用例比主逻辑更值钱写主逻辑只要几分钟但把边界用例列完整可能需要更久。空串、全 0、单字符、两种字符交替出现每一个都可能藏着一个 bug。我在实际写这道题时花在边界测试上的时间比写代码多得多效果也立竿见影。6.3 多知道几种解法但提交用最稳妥的一种多种解法不是用来炫技的是为了帮你理解题目的各种侧面。段数计数法、首尾夹逼法、查 “01” 的 Trick、正则表达式每多知道一种对“连续 1 字段”这个概念的理解就深一层。但提交到 LeetCode 上我会选择最不依赖题目约束、最不容易出错的那一版。毕竟在线评测只关心结果对不对不关心你写得有多花哨。LeetCode 1784 这道题本身不难但把它吃透之后你会发现在很多字符串题、滑动窗口题、二分判定题里都能看到类似的思路影子。下次再遇到“给你一个字符串判断是否满足某种形状”的题不妨回想一下今天这个“连续 1 字段检查”的拆解过程先定义清楚再翻译成状态切换最后用边界用例兜底。这套打法比单刷一百道题都好用。