【算法精讲】十-二进制数最少数目问题：从暴力到最优解的完整推导

本文适合算法入门学习者、面试刷题人群，全程拆解“十-二进制数最少数目”问题的解题思路，从暴力思路到最优解，附带完整代码与复杂度分析，助力理解核心逻辑。

一、问题背景与核心定义

1.1 问题描述

给定一个表示十进制整数的字符串 n（无前置零、仅由数字组成），返回和为 n 的十-二进制数的最少数目。

1.2 关键概念：十-二进制数

• 定义：十进制数字，不含任何前导零，且每一位上的数字只能是 0 或 1。
• 示例：101、1100 是十-二进制数；112（含数字2）、3001（含数字3）、011（前置零）不是。

1.3 示例理解

• 输入 n = "32"，输出 3：10 + 11 + 11 = 32（3个十-二进制数是最少的）；
• 输入 n = "82734"，输出 8：最少需要8个十-二进制数相加；
• 输入 n = "27346209830709182346"，输出 9：包含数字9，最少需要9个。

二、解题思路推导：从暴力到最优

2.1 暴力思路（不可行，但理解核心）

思路分析

暴力思路是“构造所有可能的十-二进制数组合，找到和为n的最小个数”，但存在两个致命问题：

结论

暴力思路仅适用于极短的n（如长度≤3），实际工程中完全不可用，需寻找数学规律。

2.2 核心规律：从“位贡献”角度分析

关键观察

十-二进制数的每一位只能贡献 0 或 1 到对应位置的和。例如：

• 对于n的某一位数字 d（比如“32”的十位是3），要凑出这个 d，需要至少 d 个十-二进制数在该位上贡献 1（因为每个数最多贡献1）；
• 全局来看，n中最大的单个数字，就是所需的最少数目（因为最大数字的位置决定了最少需要的数的个数，其他位置的数字都≤这个最大值，可通过“0/1组合”凑出）。

规律验证

• 示例1：n = "32" → 最大数字是3 → 输出3；
• 示例2：n = "82734" → 最大数字是8 → 输出8；
• 示例3：n = "27346209830709182346" → 最大数字是9 → 输出9。

2.3 最优解思路

三、完整代码实现（Python）

3.1 标准解法（类形式，适配LeetCode）

class Solution:
def minPartitions(self, n: str) –> int:
"""
计算和为n的十-二进制数的最少数目
:param n: 表示十进制数的字符串（无前置零）
:return: 最少需要的十-二进制数个数
"""
max_digit = 0 # 初始化最大数字为0
for char in n:
current = int(char) # 字符转数字
if current > max_digit:
max_digit = current
# 提前终止优化：9是单个数字最大值，无需继续遍历
if max_digit == 9:
break
return max_digit

# 测试用例验证
if __name__ == "__main__":
solution = Solution()
# 示例1
print(solution.minPartitions("32")) # 输出：3
# 示例2
print(solution.minPartitions("82734")) # 输出：8
# 示例3
print(solution.minPartitions("27346209830709182346")) # 输出：9

3.2 极简写法（一行代码，适合快速刷题）

def minPartitions(n: str) –> int:
return max(int(c) for c in n)

# 测试
print(minPartitions("32")) # 3

四、复杂度分析

4.1 时间复杂度

• 最坏情况：遍历整个字符串（如n全由8组成），时间复杂度为 O(len(n))；
• 最优情况：遍历到第一个9就终止（如n开头是9），时间复杂度为 O(1)；
• 整体：O(len(n))，完全适配题目中 n.length ≤ 10^5 的要求。

4.2 空间复杂度

仅使用了常数个变量（max_digit、current 等），空间复杂度为 O(1)，无额外空间开销。

五、关键注意事项

5.1 避免大数溢出

题目中n的长度可达10^5，绝对不能将n转换为整数（Python的int虽支持大数，但其他语言如Java/C++会直接溢出），必须直接遍历字符串。

5.2 提前终止优化

当遍历到数字9时，可直接返回9（因为9是单个数字的最大值，不可能有更大的值），这能大幅减少长字符串的遍历时间（比如n长度为10^{5，但第10位就是9，只需遍历10次而非10}5次）。

5.3 边界用例测试

六、总结与拓展

6.1 核心知识点回顾

6.2 拓展思考

• 若题目改为“求十-二进制数的最大数目”，该如何解？（答案：n的每一位数字相加，因为每个十-二进制数最多贡献1，最大数目就是所有位的和）；
• 若十-二进制数的定义改为“每一位是0/1/2”，最少数目该如何计算？（答案：n中每一位数字向上取整除以2的最大值）。

6.3 刷题建议

本题属于“找规律型”算法题，这类题目往往暴力解不可行，需要通过小例子推导核心规律。建议：

欢迎在评论区交流：你还遇到过哪些“看似复杂，实则找规律”的算法题？