leetcode 2026-03-01 每日一练 - 十-二进制数的最小数目

Austoin2026-03-012026-03-01

题目描述

LeetCode 1689. 十-二进制数的最小数目

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1，那么该数字就是一个十-二进制数。例如，101 和 1100 都是十-二进制数，而 112 和 3001 不是。

给你一个表示十进制整数的字符串 n，返回和为 n 的十-二进制数的最少数目。

示例：

输入：n = "32"
输出：3
解释：10 + 11 + 11 = 32

解题思路

核心观察

要用最少的十-二进制数相加得到 n，关键在于：

十-二进制数的每一位只能是 0 或 1
要得到某一位的数字 d，至少需要 d 个十-二进制数在该位上都是 1

贪心策略

答案就是字符串 n 中的最大数字。

原因：

假设 n = "321"，最大数字是 3
要得到百位的 3，至少需要 3 个十-二进制数：1xx + 1xx + 1xx
这 3 个数也可以同时满足十位的 2（11x + 11x + 10x）和个位的 1（111 + 110 + 100）
因此最少需要 3 个十-二进制数

示例验证

n = "82734"：

最大数字是 8

需要 8 个十-二进制数：

代码实现

func minPartitions(n string) int {
    ans := rune(0)
    for _, ch := range n {
        ans = max(ans, ch)
    }
    return int(ans - '0')
}

核心细节

字符与数字转换：
- 字符 '0' 的 ASCII 码是 48
- 字符 '1' 的 ASCII 码是 49
- 因此 ans - '0' 可以将字符转换为对应的数字
遍历优化：
- 只需遍历一次字符串，找到最大字符
- 如果找到 '9'，可以提前返回（因为 9 是最大可能值）
贪心正确性：
- 最大数字决定了最少需要的十-二进制数个数
- 其他位的数字都可以通过合理分配这些十-二进制数来满足

复杂度分析

时间复杂度：O(n)，其中 n 是字符串长度，需要遍历一次找到最大字符
空间复杂度：O(1)，只使用常数额外空间

优化版本

可以提前终止遍历：

func minPartitions(n string) int {
    for _, ch := range n {
        if ch == '9' {
            return 9
        }
    }
    ans := rune(0)
    for _, ch := range n {
        ans = max(ans, ch)
    }
    return int(ans - '0')
}