这道题我印象挺深LeetCode 1784题号不大名字挺长Check if Binary String Has at Most One Segment of Ones简化成一句话就是——给一个只含0和1的字符串判断里面的所有1是不是都老老实实连成了一段中间没有被0隔开。这题标着Easy但我在评论区看到不少奇怪的做法有人用正则、有人用递归、还有人先把字符串拆成数组再逐项判断。其实这题考察的就一件事能不能在只扫一遍的情况下判断“连续字段”的存在性。它特别适合刚刷题没多久的人拿来练手感也适合准备周赛的人复习一下扫描加状态机的基本功。下面我把题意拆解、三种写法、边界条件、我踩过的坑还有这类字符串扫描题的延伸套路一次讲清楚。1. 题目到底在问什么先拆穿题干1.1 题干与示例的本质题目给一个二进制字符串s要求判断这个字符串里是否存在“至多一个连续1字段”。所谓连续1字段就是由连续的1组成的一个区块区块之间只能靠0或者字符串边界隔开。比如110所有1连在一起是一个字段返回true。比如1001开头一个1结尾一个1中间隔着00这里就有两个互相分离的1字段返回false。再比如101两个1之间夹了一个0同样有两个字段返回false。我第一眼看到这题脑子里冒出来的问题是到底什么样的字符串算“不合格”把几个例子摆在一起看就很清楚了1一个字符单个1算一个字段返回true0全是0没有任何1字段属于“至多一个”的情况返回true111全部连在一起返回true11011前面一段11后面一段11中间被0断开返回false“至多一个字段”这句话是题眼。很多WAWrong Answer都出在没抠清楚“至多”两个字上——全0串是合法的因为它有零个字段零不大于一。1.2 问题的等价转换如果只是硬着头皮去数字段个数事情也能做但不够漂亮。做算法题最爽的时刻就是把题干翻译成一个更简单的判断条件。我的翻译方式是这样先找到第一个1出现的位置再找到最后一个1出现的位置。如果这两个位置中间夹着任何一个0说明1被分成了两段如果没有0说明所有1天然连成一片。举个例子0011100第一个1在位置2最后一个1在位置4中间是11全是1合法。0011001第一个1在位置2最后一个1在位置5中间是100里面有0不合法。这一步转换的意义在于把一个“判断字段数量”的问题变成了“判断区间里是否有0”的问题。后者只需要找到首尾两个标记点闭着眼睛线性扫一遍中间部分就能出结果思路极好验证写出来几乎不会因为逻辑漏洞而出错。我在实际做题时发现先把题转成这种“等价条件”再去写代码比直接在原问题上堆if-else要稳得多。2. 上手开写三种解法与完整代码2.1 基线解法首尾指针夹逼最直观的写法就是按照刚才的等价转换先找第一个1和最后一个1然后检查中间区域。C 实现如下bool checkOnesSegment(string s) { int n s.size(); int first -1, last -1; for (int i 0; i n; i) { if (s[i] 1) { if (first -1) first i; last i; } } if (first -1) return true; // 没有1合法 for (int i first; i last; i) { if (s[i] 0) return false; } return true; }这里第5到第9行是一个经典的“先找起点、不断更新终点”的扫描方式。first只在第一次遇到1时被赋值last每次遇到1都会被更新。循环结束后如果first -1说明整个字符串全是0直接返回true。第11行到第14行的检查区间写起来有一种“夹逼”的快感从第一个1的位置出发一路走到最后一个1的位置眼睛只盯着有没有0。这段逻辑完全贴合我们前面推导的等价条件干净利落。有读者可能会问为什么不在同一个循环里顺便把区间检查做了当然可以但那样逻辑会混在一起容易出错。先扫描定位再扫描检查两个循环虽然都是O(n)但各自职责清晰调试起来也方便。代码不是越短越好是越好懂越好。2.2 一次性扫描状态机思路如果在面试或周赛里想秀一点优雅可以用“状态机”的写法全程只扫一遍用一个变量记录当前处于哪个阶段。我把状态设计成三种状态0还没见过任何1状态1正在某个1字段内状态2已经见过一个完整的1字段并且这个字段已经结束了遍历每个字符时遇到1如果当前状态是2说明前面已经有字段结束了现在又冒出来新的1字段直接返回false如果当前是0或1就进入状态1。遇到0如果当前状态是1说明这个1字段到此结束状态改成2。代码长这样bool checkOnesSegment(string s) { int state 0; for (char c : s) { if (c 1) { if (state 2) return false; state 1; } else { if (state 1) state 2; } } return true; }这个写法我第一次看到的时候觉得有点“绕”但仔细一琢磨它其实就是把现实世界里的判断逻辑抽象成了状态转移。想象你在数一段路上有几家连续的商店没有商店时是状态0正路过商店时是状态1商店区已经走完后面全是空地时是状态2。如果此时又出现一家商店地方就变得不合法了——实际上不可能在“已走完”的状态下再遇到商店除非你走回头路。这里也是一样一旦字段结束后续再来1就意味着字段断开过。状态机的写法最大的优势是它只用一遍扫描加一个整数变量空间占用是O(1)而且没有额外的字符串查找操作。这个思路在后续很多字符串题里都会复现所以值得多写几遍把状态转移画在心里。2.3 计数法数一数到底有几个字段如果你不想用状态变量也可以直接数字段个数。这个方法最“笨”但也最不容易出错而且它天然支持题目变体比如“恰好有1个字段”或者“统计字段数量并返回每个字段长度”。bool checkOnesSegment(string s) { int n s.size(); int segments 0; int i 0; while (i n) { if (s[i] 1) { segments; if (segments 1) return false; while (i n s[i] 1) i; } else { i; } } return true; }这里用了一个内层while来一口气跳过一个完整的连续1段。每跳过一个段segments加一。一旦发现segments 1直接返回false。这个写法的好处是逻辑直白到任何人都能看懂内层跳段的方式也顺手处理了11011这种多个1段的场景。顺带说一个Python版本的“一行流”return 0 not in s.strip(0)。它的思路是先把字符串两端连续的0剥掉剩下的是一个被0可能夹在内部的字符串。如果内部已经没有0说明所有1是连续的如果内部还有0说明1被0分开了。这个写法非常Pythonic但理解它需要想清楚strip只去掉两端字符不能去掉内部的0用不好会被1001这种用例坑到。实际面试时我还是建议老老实实用循环一行流适合作为写完之后的彩蛋。3. 边界条件与复杂度这题送分但不送命3.1 边界用例速查表刷题最怕的不是复杂用例而是边界用例。这题虽然简单边界情况一点都不少。我把容易踩的输入串整理成了表格方便你对着自测输入字符串预期输出原因0true零个1字段满足“至多一个”1true单个1就是一个字段000true全0零个字段111true一个字段10true只有一个1字段末尾0不影响01true只有一个1字段开头的0可忽略101false两个1字段被0隔开1001false同上11011false前后两段1中间断开000111000true中间只有一段连续的100110011false两段1中间被0隔开把这几个用例塞进你的代码里跑一遍基本上任何写法都能验证出问题。我自己习惯在写完算法后先手动跑这几个用例再提交到OJ因为OJ只会告诉你WA不会告诉你哪组数据WA自己提前验证能省掉好几轮提交。3.2 复杂度分析与库函数使用心得所有三种解法的时空复杂度都一样时间复杂度O(n)空间复杂度O(1)。其中 n 是字符串长度。这题的约束是1 s.length 1000其实怎么写都能过但我们在分析时仍然要拘谨一点原因是LeetCode的简单题也可能出现在面试的白板环节面试官会问“能不能一次遍历”“能不能O(1)空间”。如果让我说点实在的用C的find和rfind来实现首尾夹逼也是安全的。它的底层实现是线性扫描复杂度同样是O(n)而且代码更短。比如bool checkOnesSegment(string s) { int first s.find(1); if (first string::npos) return true; int last s.rfind(1); for (int i first; i last; i) { if (s[i] 0) return false; } return true; }但我不推荐在这个场景用正则表达式或者split。原因很简单正则引擎的匹配开销远高于你亲手写的循环而且它的行为在边界输入下不可控。至于split(0)然后数非空段的个数虽然能过但会产生额外的内存分配数据量一旦变大就会拖慢速度。刷题阶段养成“能不分配额外空间就尽量不分配”的习惯对后续做大数组题非常有帮助。4. 我踩过的坑与调试实录4.1 坑一把“至多一个”错当成“恰好一个”这个坑我栽得很实在。第一次写出计数法版本时我最后的判断条件是return segments 1;提交之后挂在了全是0的用例上。题目说的是“at most one segment”不是“exactly one segment”。全0串里面一个段都没有但它依然满足条件应该返回true。这种“至多”和“恰好”的区别在LeetCode上经常出现比如判断字符串是否只含元音、判断数组是否非递减之类的题稍不注意就会把量词搞反。我的经验是读题时把量词圈出来——at most one、exactly one、at least one——这三个词对应的边界完全不同。4.2 坑二自作聪明用“包含01”来判断我一开始还试过一种看起来很聪明的思路只要字符串里不包含01子串就认为1都堆在一边应该是连续的。这个判断存在反例最直接的反例是101——它不包含连续的01?等等101里其实包含01吗从位置1开始的01是有的因为101的第2、3个字符就是0和1合起来是01所以按“不包含01”判断会返回 false没毛病。但反例是0011100这个字符串中间包含了一次从0到1的转变所以包含01但它只有一个1字段应该返回true。用“包含01”来判断就把它误杀了。真正等价的判断应该是从第一次出现1到最后一次出现1这个区间里不能出现0。或者用状态机的语言说一旦1字段结束后面不能再有1。所以以后遇到这种题我会先在草稿纸上写几个正反例验证一下我的等价条件是否真的等价再动手写代码。4.3 坑三把简单题做成大型工程这道题我在评论区和题解里看到有人用并查集、DP、正则表达式属实是杀鸡用牛刀了。并不是说这些技术不好而是Easy题出现在笔试里时它考察的是你能否用最朴素的手段快速解决。如果你给自己加戏比如写一个自动机框架或者用回溯去枚举所有分割方案不仅代码量爆炸出错概率也会直线上升。我自己有一个原则简单题写完先跑一遍边界用例再提交如果AC了绝不回头过度优化。想要练习高级数据结构拿Hard题去练不要拿Easy题来炫技。这题我见过有人面试时写了20分钟的正则表达式最后还没写对场面一度很尴尬。调试实录的话可以分享一个我当时的场景。输入是110011我用状态机版本从头扫读取1状态从0变1再读1状态保持1读0状态从1变2读第二个0状态保持2读到1一看状态是2直接返回false。用代码里的日志打出来转移过程一目了然。也正是这个调试过程让我彻底理解了状态机的状态定义有多重要。5. 从1784延伸字符串扫描题的通用套路5.1 状态机思想怎么复用LeetCode 1784 最好的价值不是让你背下一套解法而是让你见识一种“扫描加状态”的思考方式。很多看似不相干的题目本质上都在做同一件事线性遍历字符串同时用若干个变量记录是否需要改变状态。比如 LeetCode 1869Longer Contiguous Segments of Ones than Zeros让你判断最长连续1段的长度是否大于最长连续0段的长度。解法就是在遍历时维护当前连续字符的种类和长度遇到字符变化就更新全局最大值。它的核心代码几乎就是 1784 计数法内层while循环的加强版既要记录连续段的长度又要记录连续段的种类。再比如 LeetCode 1759Count Number of Homogenous Substrings要求统计由相同字符组成的连续子串数量。这个题在扫描时同样要维护“当前连续相同字符的长度”每次行程加长就把它累加到答案里。我个人体会是把“连续段扫描”抽象成模板之后遇到这类题可以无脑套用维护一个当前位置i和当前段类型type内层while循环一直延伸到段结束根据段的类型和长度做相应的统计或判断这套模板在字符串题里出现频率极高刷题时值得专门整理到笔记里。5.2 同类题型对比从简单题到变体题还是回到 1784 本身它的变体也相当多。最常见的变体是给定一个二进制数组只允许做一次操作把一段连续的0变成1问能不能让整个数组最终只含有一个1字段。这种变体的本质就是先统计现有1字段的数量和位置再看那个分隔的0区间能否被一次翻转补上。解法核心还是扫描分段只是多了一步“检查分段之间的空隙长度”。另一个方向是把至多一个1字段改成恰好一个1字段这时只需要把全0串的返回值从true改成false其他逻辑完全不变。我在做题时喜欢把这个变体也在本地跑一遍因为改动这么小正好可以检验我是不是真正理解了题眼而不是背代码。顺带提一个热词里的题目LeetCode 073 爱吃香蕉的狒狒。那个题跟扫描就没关系了它考的是二分查找答案。为什么提到它因为很多刚开始刷题的读者喜欢按题号顺序刷结果在简单题里遇到完全不同的考察方向容易一头雾水。我想说的是简单题也分“扫描类”和“搜索类”按考察点来刷题比按难度和题号刷效率高得多。1784 是扫描类的经典入门073 是二分答案的经典入门两个都要会但学习方法完全不同。5.3 竞赛临场策略签到题别恋战LeetCode 周赛里的第一题经常就是这种“签到扫描题”分值不大但是心态价值巨大。我个人的临场策略是第一题读完题在5分钟内用最朴素、最好验证的写法AC掉然后再看第二题。不要在一道简单题上追求“最优美解法”因为你后面还有三题等你去抢时间。如果第一题写了10分钟还没过我会强制自己停下回看是不是把题目理解偏了。70%的卡顿都出在“至多”和“恰好”、“连续”和“出现”这些模糊概念上。回到题目原文重新圈一圈关键词往往能立刻发现问题。以我的习惯这类扫描题写完以后我会顺手把segments这个变量打出来看一眼确认没有边界遗漏。有一次我写计数法时把内层while的结束条件写成了while (i n)而不是while (i n s[i] 1)导致把所有字符都跳过去了segment 永远只有1提交WA。后来就是靠打印segments发现不对的。所以别嫌打印日志土在赛场上它就是最可靠的调试手段。最后再分享一个小技巧如果你习惯用C刷题建议把string::npos的判空习惯刻在DNA里如果你用Python就多想想strip、split、count这几个字符串方法之间的等价关系。语言不同最顺手的实现也不同不必强求所有代码风格一致。但我建议至少亲手实现一遍线性扫描的版本因为面试官看重的永远是你能否把逻辑讲清楚而不是你记了多少个库函数。这道1784我做了一遍以后就再也没忘过——连续1字段检查本质就是“从第一次到最后一次中间不能有0”。