LeetCode 1422：分割字符串最大得分的单次扫描与边界条件详解

刚看到这道题的时候我第一反应是“这也能上热门 100 题”——LeetCode 1422分割字符串的最大得分题目不长逻辑也直白但仔细一琢磨它其实把“前缀和”“单次扫描”“边界条件”这几个高频考点全都揉在了一起。我提交那版用 Python 写完之后运行耗时直接显示击败 100%后面又专门把 Java 和 C 的写法都过了一遍。这篇文章就围绕 1422 这道题把从暴力思路到最优解的全过程掰开讲清楚包括我踩过的坑、写代码时的细节以及怎么把耗时优化到第一梯队。1. 题目到底在问什么读懂分割规则1.1 原题陈述与关键约束LeetCode 1422 的题面很简单给你一个由0和1组成的字符串s你需要把它分成两个非空子串左子串和右子串。这里的“非空”是硬性规定也是后面容易出 bug 的地方。得分定义为左子串中0的个数加上右子串中1的个数。目标是在所有可能的分割方式里让这个得分最大。举例来说如果输入是s 011101我们可以枚举分割点左边取0右边取11101得分为1 3 4。左边取01右边取1101得分为1 3 4。左边取011右边取101得分为1 1 2。左边取0111右边取01得分为1 1 2。左边取01110右边取1得分为4 1 5。所以最大得分是5。题目最后要求返回的就是这个最大值。约束条件里最重要的一条是字符串长度n至少是2且只包含0和1。这个约束保证了一定存在至少一个合法的分割点。还有一个隐含条件分割点必须在索引1到n-1之间因为左右两个子串都必须非空。很多同学一开始容易下意识地枚举0到n的所有分割位置那就错了。1.2 为什么“至少分割成两个非空部分”是唯一的大坑这道题的得分公式本身不复杂但它把“边界”和“统计”两件事绑在了一起。常见的错误是有人会想先统计整个字符串里1的个数然后从头往后扫每遇到一个1就把右侧得分减一每遇到一个0就把左侧得分加一最后取最大值。这个思路是对的但如果你把分割点允许放在字符串最前面或最后面就会算出不合法的答案。比如s 01合法的分割只有一种左边0右边1得分2。但如果你在索引0之前分割左边是空串右边是01得分0 1 1分母虽然能算但它不符合题意。反过来如果在索引n之后分割右边为空得分也会被算错。所以写循环的时候更新答案的时机必须放在“增加了当前字符作为左子串的一部分”之后而且要保证右子串不为空。1.3 用一个例子手算一遍为了把规则彻底搞懂我再手算一个例子s 00111长度为 5。掐着手指头枚举分割点分割点索引左子串右子串左0个数右1个数得分100111134200111235300111224400111213最大得分是 5对应分割成00和111。这里有一个值得注意的现象最优分割点不一定是最中间的也不一定是某个字符变化的转折点它完全取决于左侧 0 的累计速度和右侧 1 的剩余数量。2. 暴力做法先想清楚再动手2.1 枚举所有分割点拿到题目第一反应肯定是从头到尾枚举分割位置每个位置都重新扫一遍左右两侧统计左侧 0 的个数和右侧 1 的个数然后更新最大值。伪代码大概是def maxScore(s: str) - int: n len(s) ans 0 for i in range(1, n): # 分割点只能从 1 到 n-1 left_zeros s[:i].count(0) right_ones s[i:].count(1) ans max(ans, left_zeros right_ones) return ans这种写法的优点是几乎不可能写错适合用来快速验证自己的思路。但缺点是每一次枚举都要把两个子串重新遍历一遍count内部是O(len)的操作所以总复杂度是O(n^2)。在 LeetCode 的评测数据中n最大可以到10^5量级O(n^2)是绝对过不去的会直接超时。2.2 复杂度分析和它的问题暴力写法的问题本质在于我们重复统计了大量信息。当分割点从i移动到i1时左侧只多了一个字符s[i]右侧只少了一个字符s[i]但暴力写法却把左右两侧全部重新数一遍。这就像你每天统计公司整层楼的用电量明明昨天已经看过一遍今天却非要再走一遍所有工位。这种“重复劳动”有一个经典的解法思路维护一个“滑动窗口状态”。我们不需要每次从头算只需要在上一次的结果上做增量更新。用这个思路去优化暴力写法就自然能引出前缀和或者单次扫描的解法。2.3 从暴力代码里提炼出来的“更新技巧”假设我们已经知道了当前位置i的左侧 0 个数leftZeros以及右侧 1 个数rightOnes。当分割点向右移动一位也就是把s[i]从右子串划到左子串时如果s[i] 0那么左侧 0 个数加 1右侧 1 个数不变。如果s[i] 1那么左侧 0 个数不变右侧 1 个数减 1。所以得分的变化完全取决于新划入的字符。这个增量思路就是最优解的基础。换句话说你不需要每次重算所有东西只需要维护两个变量从左到右“滚”一遍就够了。3. 最优解法一次扫描 动态维护分数3.1 核心想法把“左侧0个数”和“右侧1个数”拆开看我们先定义两个变量leftZeros当前分割点左侧子串中0的个数。rightOnes当前分割点右侧子串中1的个数。初始时分割点在索引1前面也就是左子串只包含s[0]右子串包含从s[1]到末尾的所有字符。所以leftZeros 1 if s[0] 0 else 0rightOnes则需要统计s[1:]中1的个数。然后从i 1开始向右移动分割点。每移动一步字符s[i]会从右侧跑到左侧。我们需要更新两个变量并且在“更新之前”或“更新之后”计算当前得分取决于你希望分割点位置怎么定义。细节上稍微想清楚代码就不容易错。3.2 两次遍历的写法作为过渡很多题解喜欢用前缀和数组先统计每个位置左侧 0 的个数和右侧 1 的个数然后再遍历分割点。这样写思路最直白也最容易向面试官解释。Python 代码可以这样写def maxScore(s: str) - int: n len(s) left_zeros [0] * (n 1) for i in range(n): left_zeros[i 1] left_zeros[i] (1 if s[i] 0 else 0) right_ones [0] * (n 1) for i in range(n - 1, -1, -1): right_ones[i] right_ones[i 1] (1 if s[i] 1 else 0) ans 0 for i in range(1, n): # 分割点左边为 [0, i)右边为 [i, n) ans max(ans, left_zeros[i] right_ones[i]) return ans这里left_zeros[i]表示s[0:i]中 0 的个数right_ones[i]表示s[i:n]中 1 的个数。这种写法的好处是清晰、不易出错坏处是开了两个长度为n1的数组空间复杂度是O(n)。对这道题来说完全没有必要。3.3 真正的 O(n) O(1) 单次遍历是怎么做到的我们其实不需要把前缀和存下来。先预处理出整串中 1 的总数totalOnes然后初始化leftZeros 0rightOnes totalOnes。接着从左到右遍历把当前字符s[i]从“右侧”划到“左侧”。在划入之前s[i]还在右侧在划入之后它就归左侧了。因此我们应该先更新变量再计算得分同时要保证分割点不能到字符串末尾也就是说更新完当前字符后如果当前位置不是最后一个字符才更新答案。具体逻辑如下def maxScore(s: str) - int: total_ones s.count(1) left_zeros 0 right_ones total_ones ans 0 for i in range(len(s) - 1): # 只遍历到倒数第二个字符 if s[i] 0: left_zeros 1 else: right_ones - 1 ans max(ans, left_zeros right_ones) return ans这里的关键是for i in range(len(s) - 1)。为什么不是range(len(s))因为如果我们把最后一个字符也划入左侧那么右侧就变成空串了不满足“两个非空部分”的要求。所以分割点最多只能到n-1也就是遍历下标 0 到n-2一共n-1个合法分割位置。这个写法的时间复杂度是O(n)空间复杂度是O(1)。s.count(1)本身也是一次线性遍历所以总共跑了两遍字符串但仍然是线性复杂度LeetCode 上跑出来耗时自然是 100%。4. 代码实现与每种语言要注意的细节4.1 Python 版本与逐行解释上面那个 Python 版本已经是最精简的写法了。我在本地实测的时候输入s 1111输出是3因为无论如何分割右侧 1 的个数最多是 3左侧 0 的个数永远是 0所以最大得分就是 3。这个过程里其实隐藏了一个细节当字符串全为 1 时左侧 0 的贡献永远是 0得分完全依赖右侧 1 的个数分割点越靠左越好。反过来当字符串全为 0 时右侧 1 的贡献永远是 0得分完全依赖左侧 0 的个数分割点越靠右越好。我在 Python 里还习惯写一个更紧凑的版本class Solution: def maxScore(self, s: str) - int: ans 0 left_zeros 0 right_ones s.count(1) for i in range(len(s) - 1): if s[i] 0: left_zeros 1 else: right_ones - 1 ans max(ans, left_zeros right_ones) return ans这个版本不需要额外变量存储total_ones直接通过count拿到右侧 1 的初始值。注意在遍历过程中遇到1时right_ones要减一因为当前字符从右侧被移到了左侧原本属于右侧的 1 已经不属于右侧了。遇到0时right_ones不用变但left_zeros加一。4.2 Java/C 版本与字符比较陷阱Java 版本要注意比较字符时用s.charAt(i) 0而不是s[i]因为 Java 的字符串不能直接按下标访问。完整写法class Solution { public int maxScore(String s) { int n s.length(); int rightOnes 0; for (int i 0; i n; i) { if (s.charAt(i) 1) rightOnes; } int leftZeros 0; int ans 0; for (int i 0; i n - 1; i) { if (s.charAt(i) 0) leftZeros; else rightOnes--; ans Math.max(ans, leftZeros rightOnes); } return ans; } }C 版本和 Java 几乎一样只要注意string可以直接用s[i]但比较字符时要写成s[i] 0别少写引号。另外 C 里std::count可以用来数 1不过我习惯手写循环因为这样对边界控制更心里有数。class Solution { public: int maxScore(string s) { int n s.size(); int rightOnes 0; for (char c : s) { if (c 1) rightOnes; } int leftZeros 0; int ans 0; for (int i 0; i n - 1; i) { if (s[i] 0) leftZeros; else rightOnes--; ans max(ans, leftZeros rightOnes); } return ans; } };注意在这类字符统计题里最容易被忽略的就是字符拼接时的类型。C 的char是数值类型比较时写s[i] 0会变成和空字符比较程序不会报错但结果全错。一定要写s[i] 0。4.3 如何跑出“耗时击败100%”的小技巧严格来说最快的时间复杂度就是O(n)因为必须至少读一次字符串才能知道 1 的总数。所以“耗时 100%”更多是常数层面的优化而不是算法层面的突破。我实测下来的几个经验不要在循环里用s.count(1)。虽然 Python 的count是 C 语言实现的很快但如果在一个循环里反复调用每次都是O(n)整体就变成O(n^2)了。减少不必要的中间变量。比如不需要维护totalOnes和rightOnes两个变量直接用rightOnes初始化为总数即可。循环时用for i in range(len(s) - 1)避免在循环体里再判断i ! n - 1省掉一次分支预测。LeetCode 的“击败 100%”其实有一定随机性有时候同样的代码第二次提交就成了 99%。所以不用太纠结这个数字重要的是算法本身是单次遍历加常数空间。5. 边界条件与踩坑实录5.1 全 0 / 全 1 串的处理全 0 串例如000合法的分割点只在索引 1 和 2。我们跑一下索引 1左0右00得分1 0 1索引 2左00右0得分2 0 2最大得分是 2。我们的代码里rightOnes初始为 0遍历到0时leftZeros加一更新ans。遍历到倒数第二个字符后leftZeros 2得分 2没问题。全 1 串例如111合法的分割点索引 1左1右11得分0 2 2索引 2左11右1得分0 1 1最大得分是 2。代码里rightOnes初始为 3遇到第一个1就减一变成 2得分 2遇到第二个1再减一变成 1得分 1。没问题。这两个极端情况特别适合拿来验证代码因为如果分割点边界写错了这两种输入最容易暴露问题。5.2 分割点必须“实实在在”分开两端我遇到过一种写法会在初始化时把整个字符串当作右侧然后循环从索引 1 开始先更新答案再移动字符。这样写会漏掉“分割点在最左边”的情况导致答案偏小。比如s 01如果循环从i 1开始先算的是左0右1没问题。但如果从i 1开始却先移动s[1] 1到左侧再算得分得到的结果就不合法。正确的思路是在遍历的过程中当前字符s[i]永远是被“新划入左子串”的字符。遍历到它时先把它纳入左侧状态再计算此时的分割得分。因为此时分割点就在i和i1之间右子串仍然包含i1到末尾所以一定是合法的。遍历到最后一个字符之前停止是因为如果把最后一个字符也纳入左侧右子串就空了。5.3 常见错误速查表错误类型错误示例正确做法出错场景枚举分割点包含空串range(n 1)range(1, n)或range(n - 1)单次扫描头尾分割点被算进去忘记更新右侧1的个数只加左侧0不减右侧1遇到1时rightOnes - 1字符串里有多个1在循环里调用count每次分割重数左右子串用维护两个变量的方式数据量大时超时字符比较写成数字s[i] 0s[i] 0C/C/Java 里尤其容易错用max但初始化为0答案可能为负数本题答案最小也是1初始化0没问题无提示如果你用 JavaScript 写这道题记得s[i]在部分老版本里是 undefined建议用s.charAt(i)或直接按索引访问但确保环境支持 ES5 以上。6. 这类题的通用套路从“计数”到“前缀和”再到“单次扫描”6.1 前缀和数组的适用场景LeetCode 1422 本质是一道“区间计数”题。给定一个字符串求某个分割点两边某种特征的个数之和。这种题最通用的解法就是前缀和先预处理出前缀数组然后O(1)查询任意区间的某种计数。如果你遇到的是矩阵、多维数组那可能要用二维前缀和。但在这里只有一维所以前缀和数组的两种经典写法——正着统计 0 的个数、倒着统计 1 的个数——已经足够应付。我在面试中通常先给面试官讲前缀和版本因为逻辑更清晰然后再主动优化到单次扫描展示你对常数空间的追求。6.2 把“右侧1”转化为“总1-左侧1”的思想单次扫描能成立的核心是发现了一个恒等式右侧 1 的个数 总 1 的个数 - 左侧 1 的个数。而左侧 1 的个数又可以通过区分当前字符是 0 还是 1 来维护。于是整个得分计算公式可以改写为得分 leftZeros (totalOnes - leftOnes)这个式子告诉我们其实我们只需要关心两个数左侧 0 的个数和左侧 1 的个数。右侧的信息完全没有单独维护的必要。这种“用全局总量减去已扫描部分”的思想在很多问题里都很有用比如买卖股票的最佳时机、连续子数组的最大和、字符串中的最长不重复子串本质上都涉及“维护已扫描部分的状态再结合全局信息做判断”。6.3 进阶练习题推荐如果你做完了 1422想趁热打铁练一下类似的思路我推荐几个LeetCode 121买卖股票的最佳时机维护“已经看到的最小值”和“当前收益”的单次扫描。LeetCode 1712将数组分成三个子数组的方案数前缀和加双指针。LeetCode 2270分割数组的方案数同样是找分割点满足某个条件。LeetCode 1013将数组分成和相等的三个部分用前缀和判断区间和。周赛 430 里也有不少题会用到“分割点枚举 动态维护”的思路做完 1422 再去看会轻松很多。这些题目和 1422 共享同一套底层思维先枚举分割点再想办法用增量更新替代重复遍历。掌握了这个套路你在面试中遇到类似问题就有了一个稳定的思考框架。我个人在刷这题的时候最大的感受是不要在暴力优化的第一步就想“单次扫描”。先写前缀和再把它压缩成两个变量这样的思维链条更不容易错。等到你刷多了看到这种“左右统计”的题就会条件反射。最后再分享一个小技巧提交前一定要在本地跑一遍全 0 和全 1 的用例这俩用例能帮你挡掉 90% 的边界错误。刷题这件事很多时候不是思路有多惊艳而是细节够不够稳。