1689. 分割数字的最小数目

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 <= 10^5
• n 由数字组成
• n 不含任何前导零并且表示一个正整数

解题思路

这道题的关键在于理解什么是十进制二进制数以及如何最小化分割数目。

核心观察： 十进制二进制数的每一位只能是 0 或 1，这意味着：

1. 对于数字 n 的每一位，我们只能通过多个十进制二进制数在该位上贡献 1 来构成
2. 如果某一位是数字 d，那么我们至少需要 d 个十进制二进制数在该位上都贡献 1

贪心策略： 为了最小化十进制二进制数的总数，我们应该让每个十进制二进制数尽可能地在多个位上贡献 1。但由于每个十进制二进制数的位数可以不同，关键约束来自于数字中的最大位数字。

推理过程：

• 假设 n 中最大的数字是 max_digit
• 我们至少需要 max_digit 个十进制二进制数
• 我们可以构造恰好 max_digit 个十进制二进制数来实现目标

构造方法： 对于每一位数字 d，我们让前 d 个十进制二进制数在该位上贡献 1，其余贡献 0。

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

代码实现

class Solution {
public:
    int minPartitions(string n) {
        int maxDigit = 0;
        for (char c : n) {
            maxDigit = max(maxDigit, c - '0');
        }
        return maxDigit;
    }
};

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

public class Solution {
    public int MinPartitions(string n) {
        int maxDigit = 0;
        foreach (char c in n) {
            maxDigit = Math.Max(maxDigit, c - '0');
        }
        return maxDigit;
    }
}

/**
 * @param {string} n
 * @return {number}
 */
var minPartitions = function(n) {
    let maxDigit = 0;
    for (let c of n) {
        maxDigit = Math.max(maxDigit, parseInt(c));
    }
    return maxDigit;
};

复杂度分析

其中 n 是字符串的长度。我们需要遍历整个字符串一次来找到最大数字，使用常数额外空间。