🍢 初学者友好指南 “Partitioning Into Minimum Number Of Deci-Binary Numbers” - 第1689题 (C++, Python, JavaScript)

Source: Dev.to

问题概述

给定：
一个表示非常大的正整数的字符串 n。

目标：
找出能够相加得到 n 的 十进制二进制 数（仅由数字 0 和 1 组成）的最少数量。

直觉

加法是逐位进行的。十进制二进制数在任意十进制位上只能贡献 0 或 1。

• 如果个位出现数字 7，则至少需要 7 个十进制二进制数来提供足够的 1 以凑成 7。
• 其他数字（例如 2 或 3）可以通过在这些位置上使用 0 来满足。

因此，限制因素 就是字符串中 最大数字。
如果字符串中出现 9，就需要 9 个十进制二进制数；如果最大数字是 3，则需要 3 个。

示例讲解

示例 1：n = 32

• 数字：3（十位）和 2（个位）。
• 十位需要至少三个 1 → 10 + 10 + 10。
• 个位需要两个 1 → 11 + 11 + 10 = 32。
• 使用的总数：3（即最大数字）。

示例 2：n = 82734

• 数字：8, 2, 7, 3, 4。
• 最大数字是 8。
• 必须有 8 个独立的数；其他位置可以用不超过 8 个 1 来构造。
• 结果：8。

代码块

C++

class Solution {
public:
    int minPartitions(string n) {
        int maxi = 0;
        for (char c : n) {
            // Convert character to integer and track the maximum
            if (maxi  int:
        # The result is simply the maximum digit in the string
        # We convert the characters to integers to find the max
        return int(max(n))

JavaScript

/**
 * @param {string} n
 * @return {number}
 */
var minPartitions = function(n) {
    let maxi = 0;
    for (let i = 0; i  maxi) {
            maxi = digit;
        }
        // Optimization: if we find a 9, we can stop early
        if (maxi === 9) return 9;
    }
    return maxi;
};

关键要点

• 贪心思路： 数据集中的最大值往往决定了整个集合的需求。
• 字符串操作： 对于超出标准整数范围的巨大数字（如 10^{100000}），应将其视为字符串处理。
• 复杂度： 该解法的时间复杂度为 O(n)（n 为字符串长度），额外空间复杂度为 O(1)。

最后思考

这个问题在技术面试中会带来一个 “恍然大悟” 的时刻。它看似是动态规划或划分问题，实则是对观察力的考察。在实际的软件工程中，这类似于 资源分配：并行任务的总执行时间往往受单个最长任务的限制，就像我们的求和受最大数字的限制一样。