难度: Medium
如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。
给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。
示例 1：
输入：n = "32" 输出：3 解释：10 + 11 + 11 = 32
示例 2：
输入：n = "82734" 输出：8
示例 3：
输入：n = "27346209830709182346" 输出：9
提示：
1 <= n.length <= 105n 仅由数字组成n 不含任何前导零并总是表示正整数运行时间: 32 ms
内存: 16.8 MB
class Solution:
def minPartitions(self, n: str) -> int:
for i in range(10)[::-1]:
if str(i) in n:
return i
题解的核心思路是寻找给定数字字符串 n 中的最大数字字符。由于每个十-二进制数的数字只能是 0 或 1，因此要使若干个十-二进制数之和等于一个具体的十进制数，至少需要等于该十进制数中的最大数字的十-二进制数的数量。例如，如果 n 中的最大数字是 8，则至少需要 8 个十-二进制数相加，以保证它们的和能覆盖每个位置上的数值，这是因为每个十-二进制数的每位数字只能为 0 或 1。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minPartitions(self, n: str) -> int:
# 遍历数字从 9 到 0
for i in range(10)[::-1]:
# 如果数字 i 出现在字符串 n 中，则它是最大的数字
if str(i) in n:
return i # 返回这个最大数字，即最少需要的十-二进制数数量
在该问题中，我们的目标是找出最少的十-二进制数的数目，使得它们的和能表示数字字符串 n。十-二进制数只包含数字 0 或 1。因此，为了确保能够通过叠加这些十-二进制数来达到任何给定位置上的数字，我们至少需要的十-二进制数的数量必须等于 n 中出现的最大数字。具体到每个位置的数字并不重要，因为只要我们有足够多的十-二进制数（等于最大数字），我们就可以通过合适的配置（设置1的位置）来保证每个位置的数位要求都被满足。
是的，一旦在字符串 n 中找到最大的数字，继续检查更小的数字确实是多余的。因为我们需要的十-二进制数的数量是由 n 中的最大数字决定的。如果最大数字已经确定，那么无需继续检查其他数字，因为它们不会影响结果。
算法的效率在这种情况下仍然是高效的，因为算法主要是遍历一次字符串 n 来查找最大的数字。这个步骤的时间复杂度为 O(m)，其中 m 是字符串 n 的长度。因此，即使 n 的长度非常长（如超过100000位），时间复杂度仍然基于线性关系，适用于处理大规模数据。
算法在这种情况下仍然有效。如果 n 中包含了从 0 到 9 的每一个数字，那么最大数字是 9，根据算法逻辑，我们需要 9 个十-二进制数来确保能够表示 n。无论 n 的长度多长，只要最大数字是 9，我们就需要 9 个十-二进制数来满足条件。因此，算法在处理包含所有数字、长度非常长的字符串时效率和结果都是正确的。