LeetCode 1689 这道题的标题里其实已经把答案写在脸上了十-二进制数 脑筋急转弯。我第一次刷到它是在一次周赛练题时第一反应是这题该不会要枚举吧——毕竟要把一个数拆成若干个每位只有 0 和 1的数之和听起来就像个搜索题。等我看到 n 是一个长度最多 10^5 的字符串时才意识到这题根本不打算让你拆数。官方示例 82734 输出 827346209830709182346 输出 9稍微盯两眼就会发现答案就是整个字符串里最大的那一位数字。于是这个最少数目问题最终退化成了最朴素的操作——一次遍历比大小。1. 这道题真正的题眼加法进位在帮倒忙1.1 先搞清楚十-二进制数到底是个什么东西题目里的 deci-binary number 翻译过来叫十-二进制数名字很劝退其实定义极其简单一个十进制整数它的每一位数字只能是 0 或 1而且不能有前导零。比如 101、1100、10、1 都是合法的十-二进制数而 112 不是因为百位出现了 23001 也不是因为千位是 3。所以它本质上就是用十进制写法写的、每一位不超过 1 的数只是起了个听起来像科幻设定的名字。LeetCode 给了你一个十进制正整数 n形式是字符串长度最大能到 10^5。要求你用最少数量的十-二进制数相加恰好等于 n返回这个最小数量。直接看示例会更直观输入 n输出一种可行拆法32310 11 11827348三个示例里最难拆的后面会完整走一遍构造273462098307091823469这个超长数每一位最大就是 9答案被封死在 9看到82734 输出 8这个结果加上第三个例子十多万位数答案也没超过 9你应该警觉这道题的结果和数位复杂度无关答案被某个全局性质锁死了。1.2 如果不用脑筋急转弯你大概率会写出一堆超时代码正常刷题多了最少两个字一出现第一反应就是 DP 或 BFS。有人会定义 dp[i] 表示前 i 位最少需要多少个十-二进制数有人想从 0 开始 BFS 扩展还有人会想贪心每轮选一个与剩余数字每位对齐的十-二进制数减掉。这些思路在小数据下都能跑通但题目把 n.length 拉到了 10^5 位C 的 long long 连这个数的零头都存不下更别提逐位做减法或者维护状态转移。搜索树直接指数爆炸。出题人其实是故意把数据范围做大的。如果 n 只有三位32 你用搜索也能算出 3反而掩盖了真正的数学结论。所以当你看到长度 10^5 这种离谱的数据范围优先应该思考的是答案是否根本不依赖具体的大数运算而是由一个 O(L) 甚至 O(1) 的不变量决定。这就是脑筋急转弯类题目的典型信号。1.3 每位最多贡献 1这句话严格说并不自洽我翻了这道题下面不少高赞题解普遍是一句话带过每个十-二进制数在任意一位最多贡献 1所以 n 的第 i 位数字是 d_i就至少需要 d_i 个这样的数。你细想一下这个推理其实跳过了加法进位这个大 Boss。在一般十进制加法里某一位的最终数字完全可能不是由加数在该位放了多少个 1 直接决定的。举个例子95 5 100结果的百位是 1但两个加数在百位的贡献都是 0这个 1 完全是低两位进位凭空制造出来的。所以这个位是 d就需要 d 个数在这个位放 1这句话放在普通加法里根本不成立。本题最终结论是对的但如果你想真正理解为什么进位没有破坏结论需要一个把进位明确考虑进去的证明。下一节我就把这块短板补上这也是这个脑筋急转弯最值得玩味的地方。2. 下界证明用反证法把进位锁死再比大小2.1 记号约定假设答案比最大数字还小把 n 的十进制表示写成 d_{L-1}, ..., d_1, d_0其中 d_0 是个位L 是字符串长度。记 M max{d_i}也就是说 M 是 n 中最大的那一位数字。由于十进制每一位最多是 9所以 M ≤ 9。现在我们用反证法证明答案不可能小于 M。假设存在 t 个十-二进制数 a_1, ..., a_t它们的和恰好等于 n并且 t M。因为 M ≤ 9所以立刻得到 t ≤ 8。这里t ≤ 8非常关键它是后面把进位锁死的钥匙。接下来定义 c_i 为这 t 个加数中在第 i 位放 1 的个数。因为每个加数在每一位要么是 0 要么是 1所以 c_i 一定满足 0 ≤ c_i ≤ t ≤ 8。c_i 可以理解成第 i 位从这 t 个加数那里收到的原始贡献进位暂时不算在内。2.2 关键引理原始贡献都不超过 8 时进位根本不会发生我们用一个自底向上的归纳法。第 0 位个位没有更低位的进位进来因此真正参与个位求和的值就是 c_0而 c_0 ≤ 8小于 10所以个位不会向十位进位。假设第 i-1 位没有向第 i 位进位那么第 i 位实际参与求和的值也只有 c_i ≤ 8依然小于 10所以第 i 位也不会向第 i1 位进位。由数学归纳法整个加法过程的所有进位都是 0一次都不会发生。这个引理的价值在于一旦知道全程无进位每一位的最终数字就完全等于该位的原始贡献 c_i不同位之间彻底解耦。进位这个幽灵消失之后每位最多贡献 1的朴素直觉才真正变得严谨。所以这道题里真正保护答案成立的其实是十进制一位最大是 9这个天然屏障它保证了在 t ≤ 8 时没有一个位能凑够 10 去触发进位。2.3 导出矛盾最大数字只能由那几位 1 硬撑取一个位置 p使得 d_p M。由于我们刚才证明了全程没有进位所以第 p 位的最终数字 d_p 应该恰好等于 c_p。但 c_p ≤ t于是M d_p c_p ≤ t M这是一个明显的矛盾。因此假设不成立t M 不可能发生。换句话说无论你怎么拆加数的数量至少也要达到 n 中最大的那一个数字这就是严格的下界。这个证明里最漂亮的一点是反设t M而不是t 10——因为 M 最大只能是 9所以 t 最多只能是 8正好卡在进位阈值之下。如果哪天你遇到一个变体题允许数字位取到 18答案是最大位这个结论很可能就不成立了因为低位进位可以大规模地帮忙垫高高位。理解了这一点你才算真的吃透了这道脑筋急转弯而不只是背住了答案。3. 上界构造证明恰好够用而不只是至少这么多3.1 构造思路每个位置按领号排队的方式分配 1光证明答案至少是 M 还不够万一 M 个十-二进制数根本凑不出 n 呢所以还得构造一组正好 M 个的拆法证明上界 M 可达。构造规则异常简单。设 M max{d_i}我们准备 M 个加数 b_1, ..., b_M。对第 i 位规则是如果 d_i ≥ k那么 b_k 的第 i 位就放 1否则放 0。换成大白话第 i 位需要 d_i 个 1就像这一位发放 d_i 张入场券编号从 1 到 d_i 的加数可以在这位放 1编号更大的加数在这一位放 0。每一位都独立执行这个规则。这个构造像一个逐层铺台阶的过程如果某一位的数字是 8那 8 个加数都要在这一位贡献 1如果某一位数字只有 2那只有前两个加数在这一位放 1剩下的 6 个加数在这一位全部放 0。每位之间互不干扰。3.2 拿 82734 完整走一遍构造过程以官方第二个示例 n 82734 为例。从高位到低位分别是 d_4 8d_3 2d_2 7d_1 3d_0 4所以 M 8。按规则构造 8 个加数加数万位(d48)千位(d32)百位(d27)十位(d13)个位(d04)数值b11111111111b21111111111b31011110111b41010110101b51010010100b61010010100b71010010100b81000010000把它们对齐相加11111 11111 10111 10101 10100 10100 10100 10000 -------- 82734逐位验证万位一共 8 个 1结果是 8千位有 b1、b2 两个 1结果是 2百位有 b1 到 b7 七个 1结果是 7十位有 b1、b2、b3 三个 1结果是 3个位有 b1、b2、b3、b4 四个 1结果是 4。每一位的和都不超过 9所以整个过程没有任何进位直接拼出 82734。完美。3.3 为什么这个构造一定合法而且不会触发进位合法性检查其实有三点。第一每个 b_k 的每一位确实只有 0 或 1符合十-二进制数的定义。第二没有前导零问题取一个满足 d_p M 的位置 p那么对任意 k 1...M都有 d_p ≥ M ≥ k所以这 M 个加数在 p 位全都是 1而比 p 更高的位置只会是 0 或更小的数字。哪怕某个加数的高位都是 0它的最高有效位至少也落在 p 那个 1 上去掉前导零后依然是合法的十-二进制数。第三每一位的原始贡献恰好是 d_i总和最多 9不会产生进位所以逐位相加的结果就是 n 本身。到这里下界和上界就闭环了答案既不可能小于 M又确实能只用 M 个加数拼出来所以最终答案精确等于 M也就是字符串里最大的数字字符。4. 一行代码与细节一次遍历比大小的三种实现4.1 核心代码短到令人怀疑因为结论就是找到最大数字字符代码自然短得离谱。我个人觉得这道题最大的娱乐价值就在这一个十万位的输入最终解法只有一行。Pythonclass Solution: def minPartitions(self, n: str) - int: return int(max(n))Javaclass Solution { public int minPartitions(String n) { char best 0; for (int i 0; i n.length(); i) { char c n.charAt(i); if (c best) { best c; if (best 9) { break; } } } return best - 0; } }Cclass Solution { public: int minPartitions(string n) { char mx 0; for (char ch : n) { mx max(mx, ch); } return mx - 0; } };Python 的 max(n) 之所以能直接用是因为字符串在 Python 里按字符的 Unicode 码点比较大小而数字字符 0 到 9 的码点恰好是连续递增的所以 max(n) 返回的就是最大的那个数字字符。int() 再把它转成整数结束。4.2 为什么不能把整个 n 先转成整数这是这道题最常见的翻车点。n 的长度最大 10^5也就是说那是一个十万位的整数C 的 long long 和 Java 的 long 连边都摸不着直接转换会溢出或抛异常。Python 虽然支持任意大整数但你把十万位字符串转成一个大整数对象再想办法把每一位拆出来求最大值等于白白走了一趟大整数运算性能差且代码绕。正确姿势是停留在字符层面比较因为字符的大小顺序本身就是数字的大小顺序。有人会写 max(map(int, n))功能上是对的先把每个字符转成 int再取最大。但相比 int(max(n)) 多做了 L 次 int 转换。这种写法不算错只是没必要。记住一个原则能在字符串层解决的问题就不要把数字整体还原出来。4.3 边界条件、提前退出与复杂度几个容易忽略的细节我列一下。第一遇到 9 可以提前退出循环因为不可能存在比 9 更大的数字字符了。第二n 只有一位时比如 5答案是 5拆法是 1 1 1 1 11 的答案就是 1本身已经是合法的十-二进制数。第三题目保证 n 是正整数所以不会出现 0但如果你拿 0 自测max 返回 0答案是 0数学上可以理解为空和题目不考这个。第四返回值用 int 完全够因为答案最大到 9。复杂度方面时间 O(L)空间 O(1)L 是 n 的长度。无论 n 是三位还是十万位都只做一次线性扫描。这也是为什么这题虽然标着 Medium但最优解只有一行——规模大只是逼你放弃复杂算法并不是真的需要复杂处理。4.4 实测里的一些感想我自己在本地跑过几个极端用例包括一个全部由 9 组成的十万位字符串答案稳定输出 9耗时基本可以忽略。我还见过有人拿到这道题先写 BFS输入 32 能过一到超长案例立刻 TLE。这种样例轻松过、大样例秒超时的题最能检验你是不是真的理解了数据范围的含义。正确提交时说实话会有一种我是不是漏看了什么的错觉因为代码实在太简单了。5. 从脑筋急转弯到通法这类题还能怎么迁移5.1 识别脑筋急转弯题目的三个特征刷多了你会发现这类题目是有共同特征的。第一数据范围大得反常大到逼你放弃动态规划和搜索本题直接给你 10^5 位第二每个操作或加数存在明显的位级限制比如本题每个加数的每一位只能是 0 或 1第三存在一个非常简单的下界或上界并且还能被构造证明可达。三个特征凑齐基本就是脑筋急转弯题别再往复杂方向想。一个更实际的建议是当你脑中蹦出一个答案也太简单了吧的结论时别急着高兴先花一分钟做两个检查。第一个检查这个下界有没有忽略进位、借位、覆盖这类全局耦合效应第二个检查我能不能真的构造出一组方案恰好达到这个下界两个检查都通过再写代码提交。如果构造不出来说明下界太松正确答案大概率不是它。5.2 位视角下的同类题LeetCode 1558 与 2139脑筋急转弯不是孤例而是一类题型。和本题思路最近的是 LeetCode 1558Minimum Numbers of Function Calls to Make Target Array。给你一个全 0 数组每次操作要么给某个元素加 1要么给所有元素整体乘 2问变成 target 数组最少要几步。这题最帅的解法是逆向思考乘 2 的逆向是整体右移一位加 1 的逆向是减 1。最后你会发现答案等于所有元素的二进制表示中 1 的个数之和再加上全体元素右移到 0 的整体次数也就是最大数的二进制长度减 1。这和本题的位级独立性如出一辙只是从十进制换到了二进制。再看 LeetCode 2139Minimum Moves to Reach Target Score。从数字 1 开始每次可以加 1 或乘 2要求到达 target 的最少步数。解法也是从 target 倒推如果是奇数就减 1如果是偶数就除以 2直到回到 1。核心同样是乘 2 看成二进制整体左移加 1 看成某一位的置位操作。这类题目只要把操作翻译到位的视角复杂问题就退化成了统计或贪心和本题的一次遍历比大小在思维上完全同源。5.3 我的复盘习惯把直观解和严格证明分开记最后聊一个我自己的做题习惯。复盘一道脑筋急转弯题时我会把直观解、严格证明、反例尝试三件事分开记录。直观解帮你在周赛里快速 AC严格证明帮你在面试追问下站得住脚反例尝试则是尝试篡改题目的某个条件看看结论还成不成立。比如把本题改成允许每位数字到 18答案还是不是最大位大概率不是。这种变体思考才是刷题收获最大的部分也是判断你是不是真的理解了一道的试金石。LeetCode 1689 这道题我见过很多人秒出答案但被追问低位进位为什么不会影响结论时愣住。结论本身确实简单但能把进位锁死这个关键讲明白的人很少。希望这篇拆解能帮你把这最后一块拼图补上。下次周赛再遇到这种答案小得反常的题你也能一边敲一行代码一边在脑子里把整个证明圆得明明白白。