LeetCode 1422 分割字符串的最大得分正好是我刷题清单里的第 100 题题目标着 Easy代码量也不大。但我从读题、推导到把 Python、C、Java 三个版本全部跑通前后确实花了接近 100 分钟大头不是代码本身而是花在把边界条件彻底想清楚。如果你不想只是对着题解划走想把这道题真正吃透这篇复盘应该对你有用。全文会从题意拆解开始把暴力解、线性扫描的推导、三种实现、以及各种翻车点逐一摊开。1. 题目拆解先搞清楚得分规则1.1 一句话概括题意LeetCode 1422 给的输入是一个只包含 0 和 1 的字符串 s要求你把它切成两个都非空的子串左边一部分、右边一部分。得分 左子串里 0 的个数 右子串里 1 的个数要你求出所有合法切分方式中的最大得分。举例s 011101如果切在第 1 个字符后面左子串是 0里面有 1 个零右子串是 11101里面有 4 个一得分是 1 4 5。如果切在第 2 个字符后面左子串是 01零有 1 个右子串是 1101一有 3 个得分是 4。把所有切分位置都算一遍最大值就是 5。1.2 三个容易忽略的细节这一题描述很短但真正动笔之前有三个细节必须钉死否则后面代码一定出问题。第一两个子串都必须非空。也就是说切分点只能落在 1 到 n-1 之间不能切在开头让左边为空也不能切在结尾让右边为空。这个限制看起来非常显然但写循环的时候非常容易手滑写成 for i in range(n)把右边为空的情况也当成了合法方案。第二字符是 0 和 1不是数字 0 和 1。统计的时候要比较字符别把类型弄混。C 里可以直接 if (s[i] 0)Python 里也是 0不需要 int() 转换多一层转换就多一个出错点。第三题目给出的数据范围是 2 s.length 500。这个范围意味着即使你写一个 O(n^2) 的暴力解法也能通过不会超时。但我不建议看到数据小就直接暴力提交后面会说为什么 O(n) 的思路更值得掌握。1.3 这道题到底在考什么从标签上看它属于字符串和枚举从刷题角度看它真正考的是前缀统计这个基础工具。所谓前缀统计就是在一次从左到右的遍历过程中不断维护到当前位置为止的某些统计量比如 0 的个数、1 的个数、和、最大值等。这类题的共同特征是答案需要你考虑所有切分位置但每个位置的统计并不需要真的重新扫一遍整段区间。另外也想提醒一点这题不是动态规划也不是贪心。有些人看到最大得分就下意识想 DP那是想多了。切分点是唯一的得分规则是两个独立计数的相加不存在状态转移更不存在局部最优组成全局最优的推导。它就是一道老老实实的枚举题只是枚举的方式有讲究。2. 解题思路演进从两重循环到一次遍历2.1 暴力枚举法先把正确性做出来最直接的想法把所有合法切分位置都试一遍每一次分别统计左边 0 的个数和右边 1 的个数更新最大值。class Solution: def maxScore(self, s: str) - int: n len(s) ans 0 for i in range(1, n): score s[:i].count(0) s[i:].count(1) ans max(ans, score) return ans这段代码在正确性上没有毛病复杂度是 O(n^2)。原因在于 s[:i].count(0) 和 s[i:].count(1) 每次都要把对应的子串从头到尾扫一遍而切分点有 n-1 个所以总操作量接近 n^2/2。在 n 500 的时候只有十几万次字符判断LeetCode 上跑完全没问题一般 30ms 到 50ms 之间。那为什么还要往 O(n) 想两个原因。一是如果题目数据范围稍微变大比如 n 到 10^5这个解法立刻超时二是这个 O(n) 推导本身非常漂亮它是很多中等题的地基。与其等碰到中等题再学不如在这道 Easy 题上就把套路沉淀下来。2.2 一次遍历的推导过程核心观察是左边的统计量可以随着切分点右移逐步累积而右边的统计量不需要重新数它可以用全局总量减去左边已经消耗的量算出来。用变量表示一下。设 total_ones 是整个字符串里 1 的总数zeros_left 是左子串里 0 的个数ones_left 是左子串里 1 的个数。那么右子串里 1 的个数就是ones_right total_ones - ones_left于是任意切分位置的得分可以写成score zeros_left ones_right zeros_left (total_ones - ones_left) total_ones (zeros_left - ones_left)注意 total_ones 是一个固定的常数所以要最大化得分本质上只需要最大化 (zeros_left - ones_left)。这个过程对应到代码里特别简单从字符串左端开始往右走每读到一个字符就更新 zeros_left 或 ones_left然后用上式算出当前得分更新答案。唯一要注意的是循环停在倒数第二个字符保证右子串非空。这里还有一个等价的小技巧与其每次算 total_ones - ones_left不如直接维护一个 delta zeros_left - ones_left答案就是 total_ones max(delta)。两种写法结果一样我下面给的是更直白、更容易看懂的版本学有余力可以再自己改写成 delta 版本。2.3 为什么先暴力再优化是值得的我刷题的习惯永远是先保证正确性再谈效率。暴力解法最大的价值是给你一个绝对正确的基准后面优化版本跑出来的结果可以跟它对照。尤其是像 1422 这种题暴力版本只要十几行跑一遍官方样例确认输出是 5、5、1心里就踏实了。然后你再去做优化推导。你会发现优化的本质不是更快的魔法而是减少重复计算。暴力的浪费时间花在每一次切分都要重新数右边的 1 上而优化版本用 total_ones - ones_left 一句话就复用了全局统计。这种全局总量 - 左边已消耗 右边剩余的思路在算法题里出现频率极高。3. 三种语言实现与复杂度实测3.1 Python 参考实现Python 版本推荐这样写class Solution: def maxScore(self, s: str) - int: total_ones s.count(1) zeros_left 0 ones_left 0 ans 0 for i in range(len(s) - 1): if s[i] 0: zeros_left 1 else: ones_left 1 ones_right total_ones - ones_left ans max(ans, zeros_left ones_right) return ans几个注意点s.count(1) 是 Python 内部用 C 实现的跑一次开销极低不需要自己手写循环去数。for i in range(len(s) - 1) 保证最后一次循环时左子串是 s[:n-1]右子串是 s[n-1:]右边至少有一个字符。每次循环只做常数次操作总复杂度 O(n)空间 O(1)。3.2 C 与 Java 的对照写法C 版本class Solution { public: int maxScore(string s) { int total_ones 0; for (char c : s) { if (c 1) total_ones; } int zeros_left 0, ones_left 0, ans 0; for (int i 0; i (int)s.size() - 1; i) { if (s[i] 0) zeros_left; else ones_left; ans max(ans, zeros_left (total_ones - ones_left)); } return ans; } };Java 版本class Solution { public int maxScore(String s) { int totalOnes 0; for (char c : s.toCharArray()) { if (c 1) totalOnes; } int zerosLeft 0, onesLeft 0, ans 0; for (int i 0; i s.length() - 1; i) { if (s.charAt(i) 0) zerosLeft; else onesLeft; ans Math.max(ans, zerosLeft (totalOnes - onesLeft)); } return ans; } }三个语言的核心逻辑完全一致。C 里要注意 (int)s.size() - 1 这个强制转换因为 string::size() 返回的是无符号类型不转的话当 n 0 时会出现下溢虽然题目保证 n 2但写成 int 能避免很多潜在警告。Java 的 toCharArray() 会额外产生一个 char 数组介意的话可以改成 charAt 直接遍历效果一样。3.3 复杂度与实测表现方案时间复杂度空间复杂度适合场景暴力枚举O(n^2)O(n)切片或 O(1)原地计数n 很小追求最短代码线性扫描O(n)O(1)推荐任何规模都能跑我实际在 LeetCode 上提交过几次线性扫描版本Python 大概在 32ms 到 48ms 之间C 基本稳定在 3ms 以内Java 在 4ms 到 6ms。内存占用都是 O(1)不会因为字符串变长而增加额外开销。4. 踩坑记录与边界自查4.1 三个最容易翻车的点第一个坑是循环范围。写成 for i in range(n) 会把切分点推到字符串末尾此时右子串为空空串里 1 的个数是 0如果此时左子串里恰好有很多 0得分可能虚高提交就 WA。正确写法是 range(1, n)暴力版或 range(n - 1)线性版把非空限制焊死在循环里。第二个坑是统计字符时类型不统一。比如有人图省事写成 int(s[i])把 0 变成 0、1 变成 1然后靠求和来数 1 的个数。这个思路本身可以但要注意 0 转成 0 之后无法区分字符 0 的个数和字符 1 的个数容易把自己绕晕。我个人建议老老实实比较字符代码可读性最好。第三个坑是试图用贪心。有人会觉得左边 0 多、右边 1 多就得分高于是想找一个让左边全是 0、右边全是 1 的位置。但问题是字符串顺序是固定的你只能切一刀不能调整字符位置。比如 10 这个输入无论怎么切最大得分也只有 0因为切在中间后左边是一个 1贡献 0右边是一个 0贡献 0。不先跑样例就套贪心很容易得出错误结论。4.2 自查用例清单写完之后我建议至少把下面这组用例跑一遍输入期望输出备注001最短长度全 0012左 0 右 1最优结构100结构恰好相反111全 1 时最大得分是 111113全 1切第一刀得分最高0111015官方样例 1001115官方样例 2其中 00 和 01 这种长度为 2 的用例特别重要因为 n 2 时只有一个合法切分点正好能检验循环边界有没有写错。10 这类用例能帮你确认统计方向没有反。4.3 实测中的两个隐性细节第一个细节是 total_ones 的初始化。如果你把 total_ones 算错整个答案都会系统性偏移。可以用一个全 1 的短字符串比如 111 做快速验证total_ones 3然后手动推一遍很容易定位问题。第二个细节是 ans 的初始值。因为得分最小也只能是 0不存在负数所以 ans 初始化为 0 就可以。有些人习惯初始化为无穷小在这个题里没必要但如果你把规则改成左边 1 扣分、右边 0 扣分之类的变体就要重新考虑初始值了。5. 同类题扩展这套左信息 全局信息套路还能用在哪儿5.1 前缀统计的通用模式1422 这种题的核心模式可以提炼成三步第一预处理全局总量比如总 1 数第二从左到右遍历维护左边某种统计量第三用全局总量减去左边消耗量得到右边剩余量拼出当前方案的得分。这个模式在 LeetCode 里非常常见最典型的就是 724 题寻找数组的中心下标它要求找到某个位置使得左边的和等于右边的和解法就是先求总和然后从左往右维护左和右和直接用总和减左和再减当前值得到。再往远了说238 题除自身以外数组的乘积也是同一家族它需要每个位置左边所有数的乘积和右边所有数的乘积虽然实现上用了前缀积和后缀积两个数组但思想完全一样——左边一段的信息和右边一段的信息可以分别预处理最后在 O(1) 时间里合并。包括最近周赛里很多枚举分割点 维护实时状态的题目本质都是这个套路换皮。5.2 如何从这道题迁移到中等题当你遇到一道新题第一反应别急着套模板先问自己三个问题这个解法的答案需要枚举什么枚举的过程中有没有可以增量更新的量另一侧的信息能不能用全局总量减出来如果三个问题都有答案那这道题大概率就是1422 的加大版。举个具体的迁移路径假设题目改成把字符串切成两段使得左段中 0 的个数加上右段中 1 的个数最大但左右两段长度不能相等——这时候枚举的切分点范围变了一点但核心维护逻辑不变你依然只需要一次遍历。再比如改成切成三段得分是三段的某种加权和这种题就可能需要前缀和数组辅助思路仍然是从 1422 延伸出去的。5.3 我的三点实操建议第一先暴力后优化这真的不是浪费时间。暴力的代码是你在分析复杂问题时的参照系有了它优化版本跑出来对不对一眼就能对照出来。第二动笔演算样例。我第一次做这题时把 011101 的五个合法切分位置全部写在纸上每个位置手算得分五分钟后对 O(n) 公式的理解就彻底到位了。第三提交之前把长度为 2 的输入和全 0、全 1 的输入都跑一遍Java 和 C 的边界问题往往就藏在这里。最后说点个人体会。这一题我们花了 100 分钟左右代码量加起来不过几十行听起来效率不高但我觉得很值。刷题最怕的不是慢而是刷完就忘。我把推导过程、三个语言的差异、以及几个翻车点都记在笔记里之后遇到前缀统计类的题翻这一页就够了。你也不妨试试用这种把一道 Easy 题拆到骨头里的方式去对待你看过的每一道题。
LeetCode 1422 分割字符串的最大得分：前缀统计与一次遍历全解析
LeetCode 1422 分割字符串的最大得分正好是我刷题清单里的第 100 题题目标着 Easy代码量也不大。但我从读题、推导到把 Python、C、Java 三个版本全部跑通前后确实花了接近 100 分钟大头不是代码本身而是花在把边界条件彻底想清楚。如果你不想只是对着题解划走想把这道题真正吃透这篇复盘应该对你有用。全文会从题意拆解开始把暴力解、线性扫描的推导、三种实现、以及各种翻车点逐一摊开。1. 题目拆解先搞清楚得分规则1.1 一句话概括题意LeetCode 1422 给的输入是一个只包含 0 和 1 的字符串 s要求你把它切成两个都非空的子串左边一部分、右边一部分。得分 左子串里 0 的个数 右子串里 1 的个数要你求出所有合法切分方式中的最大得分。举例s 011101如果切在第 1 个字符后面左子串是 0里面有 1 个零右子串是 11101里面有 4 个一得分是 1 4 5。如果切在第 2 个字符后面左子串是 01零有 1 个右子串是 1101一有 3 个得分是 4。把所有切分位置都算一遍最大值就是 5。1.2 三个容易忽略的细节这一题描述很短但真正动笔之前有三个细节必须钉死否则后面代码一定出问题。第一两个子串都必须非空。也就是说切分点只能落在 1 到 n-1 之间不能切在开头让左边为空也不能切在结尾让右边为空。这个限制看起来非常显然但写循环的时候非常容易手滑写成 for i in range(n)把右边为空的情况也当成了合法方案。第二字符是 0 和 1不是数字 0 和 1。统计的时候要比较字符别把类型弄混。C 里可以直接 if (s[i] 0)Python 里也是 0不需要 int() 转换多一层转换就多一个出错点。第三题目给出的数据范围是 2 s.length 500。这个范围意味着即使你写一个 O(n^2) 的暴力解法也能通过不会超时。但我不建议看到数据小就直接暴力提交后面会说为什么 O(n) 的思路更值得掌握。1.3 这道题到底在考什么从标签上看它属于字符串和枚举从刷题角度看它真正考的是前缀统计这个基础工具。所谓前缀统计就是在一次从左到右的遍历过程中不断维护到当前位置为止的某些统计量比如 0 的个数、1 的个数、和、最大值等。这类题的共同特征是答案需要你考虑所有切分位置但每个位置的统计并不需要真的重新扫一遍整段区间。另外也想提醒一点这题不是动态规划也不是贪心。有些人看到最大得分就下意识想 DP那是想多了。切分点是唯一的得分规则是两个独立计数的相加不存在状态转移更不存在局部最优组成全局最优的推导。它就是一道老老实实的枚举题只是枚举的方式有讲究。2. 解题思路演进从两重循环到一次遍历2.1 暴力枚举法先把正确性做出来最直接的想法把所有合法切分位置都试一遍每一次分别统计左边 0 的个数和右边 1 的个数更新最大值。class Solution: def maxScore(self, s: str) - int: n len(s) ans 0 for i in range(1, n): score s[:i].count(0) s[i:].count(1) ans max(ans, score) return ans这段代码在正确性上没有毛病复杂度是 O(n^2)。原因在于 s[:i].count(0) 和 s[i:].count(1) 每次都要把对应的子串从头到尾扫一遍而切分点有 n-1 个所以总操作量接近 n^2/2。在 n 500 的时候只有十几万次字符判断LeetCode 上跑完全没问题一般 30ms 到 50ms 之间。那为什么还要往 O(n) 想两个原因。一是如果题目数据范围稍微变大比如 n 到 10^5这个解法立刻超时二是这个 O(n) 推导本身非常漂亮它是很多中等题的地基。与其等碰到中等题再学不如在这道 Easy 题上就把套路沉淀下来。2.2 一次遍历的推导过程核心观察是左边的统计量可以随着切分点右移逐步累积而右边的统计量不需要重新数它可以用全局总量减去左边已经消耗的量算出来。用变量表示一下。设 total_ones 是整个字符串里 1 的总数zeros_left 是左子串里 0 的个数ones_left 是左子串里 1 的个数。那么右子串里 1 的个数就是ones_right total_ones - ones_left于是任意切分位置的得分可以写成score zeros_left ones_right zeros_left (total_ones - ones_left) total_ones (zeros_left - ones_left)注意 total_ones 是一个固定的常数所以要最大化得分本质上只需要最大化 (zeros_left - ones_left)。这个过程对应到代码里特别简单从字符串左端开始往右走每读到一个字符就更新 zeros_left 或 ones_left然后用上式算出当前得分更新答案。唯一要注意的是循环停在倒数第二个字符保证右子串非空。这里还有一个等价的小技巧与其每次算 total_ones - ones_left不如直接维护一个 delta zeros_left - ones_left答案就是 total_ones max(delta)。两种写法结果一样我下面给的是更直白、更容易看懂的版本学有余力可以再自己改写成 delta 版本。2.3 为什么先暴力再优化是值得的我刷题的习惯永远是先保证正确性再谈效率。暴力解法最大的价值是给你一个绝对正确的基准后面优化版本跑出来的结果可以跟它对照。尤其是像 1422 这种题暴力版本只要十几行跑一遍官方样例确认输出是 5、5、1心里就踏实了。然后你再去做优化推导。你会发现优化的本质不是更快的魔法而是减少重复计算。暴力的浪费时间花在每一次切分都要重新数右边的 1 上而优化版本用 total_ones - ones_left 一句话就复用了全局统计。这种全局总量 - 左边已消耗 右边剩余的思路在算法题里出现频率极高。3. 三种语言实现与复杂度实测3.1 Python 参考实现Python 版本推荐这样写class Solution: def maxScore(self, s: str) - int: total_ones s.count(1) zeros_left 0 ones_left 0 ans 0 for i in range(len(s) - 1): if s[i] 0: zeros_left 1 else: ones_left 1 ones_right total_ones - ones_left ans max(ans, zeros_left ones_right) return ans几个注意点s.count(1) 是 Python 内部用 C 实现的跑一次开销极低不需要自己手写循环去数。for i in range(len(s) - 1) 保证最后一次循环时左子串是 s[:n-1]右子串是 s[n-1:]右边至少有一个字符。每次循环只做常数次操作总复杂度 O(n)空间 O(1)。3.2 C 与 Java 的对照写法C 版本class Solution { public: int maxScore(string s) { int total_ones 0; for (char c : s) { if (c 1) total_ones; } int zeros_left 0, ones_left 0, ans 0; for (int i 0; i (int)s.size() - 1; i) { if (s[i] 0) zeros_left; else ones_left; ans max(ans, zeros_left (total_ones - ones_left)); } return ans; } };Java 版本class Solution { public int maxScore(String s) { int totalOnes 0; for (char c : s.toCharArray()) { if (c 1) totalOnes; } int zerosLeft 0, onesLeft 0, ans 0; for (int i 0; i s.length() - 1; i) { if (s.charAt(i) 0) zerosLeft; else onesLeft; ans Math.max(ans, zerosLeft (totalOnes - onesLeft)); } return ans; } }三个语言的核心逻辑完全一致。C 里要注意 (int)s.size() - 1 这个强制转换因为 string::size() 返回的是无符号类型不转的话当 n 0 时会出现下溢虽然题目保证 n 2但写成 int 能避免很多潜在警告。Java 的 toCharArray() 会额外产生一个 char 数组介意的话可以改成 charAt 直接遍历效果一样。3.3 复杂度与实测表现方案时间复杂度空间复杂度适合场景暴力枚举O(n^2)O(n)切片或 O(1)原地计数n 很小追求最短代码线性扫描O(n)O(1)推荐任何规模都能跑我实际在 LeetCode 上提交过几次线性扫描版本Python 大概在 32ms 到 48ms 之间C 基本稳定在 3ms 以内Java 在 4ms 到 6ms。内存占用都是 O(1)不会因为字符串变长而增加额外开销。4. 踩坑记录与边界自查4.1 三个最容易翻车的点第一个坑是循环范围。写成 for i in range(n) 会把切分点推到字符串末尾此时右子串为空空串里 1 的个数是 0如果此时左子串里恰好有很多 0得分可能虚高提交就 WA。正确写法是 range(1, n)暴力版或 range(n - 1)线性版把非空限制焊死在循环里。第二个坑是统计字符时类型不统一。比如有人图省事写成 int(s[i])把 0 变成 0、1 变成 1然后靠求和来数 1 的个数。这个思路本身可以但要注意 0 转成 0 之后无法区分字符 0 的个数和字符 1 的个数容易把自己绕晕。我个人建议老老实实比较字符代码可读性最好。第三个坑是试图用贪心。有人会觉得左边 0 多、右边 1 多就得分高于是想找一个让左边全是 0、右边全是 1 的位置。但问题是字符串顺序是固定的你只能切一刀不能调整字符位置。比如 10 这个输入无论怎么切最大得分也只有 0因为切在中间后左边是一个 1贡献 0右边是一个 0贡献 0。不先跑样例就套贪心很容易得出错误结论。4.2 自查用例清单写完之后我建议至少把下面这组用例跑一遍输入期望输出备注001最短长度全 0012左 0 右 1最优结构100结构恰好相反111全 1 时最大得分是 111113全 1切第一刀得分最高0111015官方样例 1001115官方样例 2其中 00 和 01 这种长度为 2 的用例特别重要因为 n 2 时只有一个合法切分点正好能检验循环边界有没有写错。10 这类用例能帮你确认统计方向没有反。4.3 实测中的两个隐性细节第一个细节是 total_ones 的初始化。如果你把 total_ones 算错整个答案都会系统性偏移。可以用一个全 1 的短字符串比如 111 做快速验证total_ones 3然后手动推一遍很容易定位问题。第二个细节是 ans 的初始值。因为得分最小也只能是 0不存在负数所以 ans 初始化为 0 就可以。有些人习惯初始化为无穷小在这个题里没必要但如果你把规则改成左边 1 扣分、右边 0 扣分之类的变体就要重新考虑初始值了。5. 同类题扩展这套左信息 全局信息套路还能用在哪儿5.1 前缀统计的通用模式1422 这种题的核心模式可以提炼成三步第一预处理全局总量比如总 1 数第二从左到右遍历维护左边某种统计量第三用全局总量减去左边消耗量得到右边剩余量拼出当前方案的得分。这个模式在 LeetCode 里非常常见最典型的就是 724 题寻找数组的中心下标它要求找到某个位置使得左边的和等于右边的和解法就是先求总和然后从左往右维护左和右和直接用总和减左和再减当前值得到。再往远了说238 题除自身以外数组的乘积也是同一家族它需要每个位置左边所有数的乘积和右边所有数的乘积虽然实现上用了前缀积和后缀积两个数组但思想完全一样——左边一段的信息和右边一段的信息可以分别预处理最后在 O(1) 时间里合并。包括最近周赛里很多枚举分割点 维护实时状态的题目本质都是这个套路换皮。5.2 如何从这道题迁移到中等题当你遇到一道新题第一反应别急着套模板先问自己三个问题这个解法的答案需要枚举什么枚举的过程中有没有可以增量更新的量另一侧的信息能不能用全局总量减出来如果三个问题都有答案那这道题大概率就是1422 的加大版。举个具体的迁移路径假设题目改成把字符串切成两段使得左段中 0 的个数加上右段中 1 的个数最大但左右两段长度不能相等——这时候枚举的切分点范围变了一点但核心维护逻辑不变你依然只需要一次遍历。再比如改成切成三段得分是三段的某种加权和这种题就可能需要前缀和数组辅助思路仍然是从 1422 延伸出去的。5.3 我的三点实操建议第一先暴力后优化这真的不是浪费时间。暴力的代码是你在分析复杂问题时的参照系有了它优化版本跑出来对不对一眼就能对照出来。第二动笔演算样例。我第一次做这题时把 011101 的五个合法切分位置全部写在纸上每个位置手算得分五分钟后对 O(n) 公式的理解就彻底到位了。第三提交之前把长度为 2 的输入和全 0、全 1 的输入都跑一遍Java 和 C 的边界问题往往就藏在这里。最后说点个人体会。这一题我们花了 100 分钟左右代码量加起来不过几十行听起来效率不高但我觉得很值。刷题最怕的不是慢而是刷完就忘。我把推导过程、三个语言的差异、以及几个翻车点都记在笔记里之后遇到前缀统计类的题翻这一页就够了。你也不妨试试用这种把一道 Easy 题拆到骨头里的方式去对待你看过的每一道题。
