企业官网建设流程全解析

LeetCode 1689 这道题的标题里其实已经把答案写在脸上了："十-二进制数" + "脑筋急转弯"。我第一次刷到它是在一次周赛练题时，第一反应是这题该不会要枚举吧——毕竟要把一个数拆成若干个"每位只有 0 和 1"的数之和，听起来就像个搜索题。等我看到 n 是一个长度最多 10^5 的字符串时，才意识到这题根本不打算让你拆数。官方示例 "82734" 输出 8，"27346209830709182346" 输出 9，稍微盯两眼就会发现：答案就是整个字符串里最大的那一位数字。于是这个"最少数目"问题，最终退化成了最朴素的操作——一次遍历，比大小。

1. 这道题真正的"题眼"：加法进位在帮倒忙

1.1 先搞清楚"十-二进制数"到底是个什么东西

题目里的 deci-binary number 翻译过来叫"十-二进制数"，名字很劝退，其实定义极其简单：一个十进制整数，它的每一位数字只能是 0 或 1，而且不能有前导零。比如 101、1100、10、1 都是合法的十-二进制数；而 112 不是，因为百位出现了 2；3001 也不是，因为千位是 3。所以它本质上就是"用十进制写法写的、每一位不超过 1 的数"，只是起了个听起来像科幻设定的名字。

LeetCode 给了你一个十进制正整数 n，形式是字符串，长度最大能到 10^5。要求你用最少数量的十-二进制数相加，恰好等于 n，返回这个最小数量。直接看示例会更直观：

看到"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 位也不会向第 i+1 位进位。由数学归纳法，整个加法过程的所有进位都是 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 = 8，d_3 = 2，d_2 = 7，d_1 = 3，d_0 = 4，所以 M = 8。按规则构造 8 个加数：

把它们对齐相加：

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 核心代码短到令人怀疑

因为结论就是"找到最大数字字符"，代码自然短得离谱。我个人觉得这道题最大的娱乐价值就在这：一个十万位的输入，最终解法只有一行。

Python：

class Solution: def minPartitions(self, n: str) -> int: return int(max(n))

Java：

class 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'; } }

C++：

class 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 + 1；"1" 的答案就是 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 1558，Minimum Numbers of Function Calls to Make Target Array。给你一个全 0 数组，每次操作要么给某个元素加 1，要么给所有元素整体乘 2，问变成 target 数组最少要几步。这题最帅的解法是逆向思考：乘 2 的逆向是整体右移一位，加 1 的逆向是减 1。最后你会发现答案等于所有元素的二进制表示中 1 的个数之和，再加上全体元素右移到 0 的整体次数，也就是最大数的二进制长度减 1。这和本题的"位级独立性"如出一辙，只是从十进制换到了二进制。

再看 LeetCode 2139，Minimum Moves to Reach Target Score。从数字 1 开始，每次可以加 1 或乘 2，要求到达 target 的最少步数。解法也是从 target 倒推：如果是奇数就减 1，如果是偶数就除以 2，直到回到 1。核心同样是"乘 2 看成二进制整体左移，加 1 看成某一位的置位操作"。这类题目只要把操作翻译到位的视角，复杂问题就退化成了统计或贪心，和本题的"一次遍历比大小"在思维上完全同源。

5.3 我的复盘习惯：把"直观解"和"严格证明"分开记

最后聊一个我自己的做题习惯。复盘一道脑筋急转弯题时，我会把"直观解"、"严格证明"、"反例尝试"三件事分开记录。直观解帮你在周赛里快速 AC；严格证明帮你在面试追问下站得住脚；反例尝试则是尝试篡改题目的某个条件，看看结论还成不成立。比如把本题改成允许每位数字到 18，答案还是不是最大位？大概率不是。这种变体思考才是刷题收获最大的部分，也是判断你是不是真的理解了一道的试金石。

LeetCode 1689 这道题我见过很多人秒出答案，但被追问"低位进位为什么不会影响结论"时愣住。结论本身确实简单，但能把进位锁死这个关键讲明白的人很少。希望这篇拆解能帮你把这最后一块拼图补上。下次周赛再遇到这种"答案小得反常"的题，你也能一边敲一行代码，一边在脑子里把整个证明圆得明明白白。