当前位置：首页 > article >正文

豆包MarsCode：小C的类二进制拼图

article 2025/1/27 4:02:17

问题描述

在这里插入图片描述

思路分析

1. 类二进制数字定义

从题目中我们可以知道，类二进制数字是仅由 0 和 1 组成的数字。比如：1, 10, 100, 101, 110 等等，这些数字都是合法的类二进制数字。换句话说，类二进制数字可以看作是 “二进制表示法” 对应的十进制数。

2. 问题关键点

数字的分解：给定一个数字 n，我们需要用最少的类二进制数字相加得到它。分解问题关键在于如何通过最小的类二进制数字组合来得到 n。
观察到，n 的十进制数可以看作是由多个 类二进制数字 组合而成。

3. 解题思路

假设数字 n 为一个十进制数。我们可以把 n 看作是由若干个类二进制数字加起来构成。
例如，对于 212，我们可以拆分为 111 和 101，因为：
```
111 + 101 = 212
```
对于 9876543210，我们可以拆分成每个位置上的数字，每一位都代表一个类二进制数字。由于每个位置上的数字最大是 9，我们需要最多 9 个类二进制数字。

4. 解题策略

为了计算最少需要多少个类二进制数字：

我们可以遍历数字 n，逐位查看每一位上的数字。
关键：对于每一位上的数字 d，如果它是非零的，我们就需要 d 个类二进制数字来处理这一位。

5. 举例分析

例如，对于数字 212：

第一个数字是 2，我们需要至少 2 个类二进制数字来填补这个数字。
第二个数字是 1，我们需要 1 个类二进制数字来填补这一位。
第三个数字是 2，我们再次需要 2 个类二进制数字来填补。

因此，最少需要 2 个类二进制数字，答案是 2。

对于 9876543210：

每一位的数字都需要拆分开来，因此最少需要 9 个类二进制数字。

复杂度分析：

时间复杂度：O(k)，其中 k 是数字 n 的长度。我们需要遍历字符串中的每一位，找出最大数字。
空间复杂度：O(1)，只使用了常量空间来存储最大值。

参考代码（Java）

public class Main {
    public static int solution(String n) {
        // 记录数字 n 中的最大位
        int maxDigit = 0;

        // 遍历 n 的每一位，更新 maxDigit
        for (int i = 0; i < n.length(); i++) {
            maxDigit = Math.max(maxDigit, n.charAt(i) - '0');
        }

        // 返回最大位数值作为最少类二进制数字个数
        return maxDigit;
    }

    public static void main(String[] args) {
        System.out.println(solution("10101") == 1); 
        System.out.println(solution("212") == 2); 
        System.out.println(solution("1000000") == 1); 
        System.out.println(solution("123456789") == 9); 
        System.out.println(solution("9876543210") == 9); 
    }
}

代码分析

`solution` 方法：

这个方法的主要功能是计算最少需要多少个类二进制数字来表示给定的数字 n。

public static int solution(String n) {
    int maxDigit = 0;
    for (int i = 0; i < n.length(); i++) {
        maxDigit = Math.max(maxDigit, n.charAt(i) - '0');
    }
    return maxDigit;
}

分析：

int maxDigit = 0;
- 这里定义了一个变量 maxDigit，用来存储数字 n 中最大的一位数字。我们将用它来决定最少需要多少个类二进制数字。
for (int i = 0; i < n.length(); i++) {
- 遍历字符串 n 的每一位。n.length() 返回字符串 n 的长度。i 是遍历索引，确保每一位都会被检查。
maxDigit = Math.max(maxDigit, n.charAt(i) - '0');
- n.charAt(i) 取出字符串 n 中第 i 位的字符。
- 由于 n.charAt(i) 是字符类型，需要将其转换为数字。n.charAt(i) - '0' 就是将字符转换为对应的数字（例如字符 '2' 会被转换为数字 2）。
- Math.max(maxDigit, n.charAt(i) - '0') 的作用是更新 maxDigit，使其始终保持 n 中最大的数字。
return maxDigit;
- 返回 maxDigit，即 n 中最大的一位数字。根据我们之前的推理，n 最少需要 maxDigit 个类二进制数字来表示。

主要逻辑：

最少类二进制数字个数 = n 中的最大数字。
- 这是因为每个数字表示的值决定了我们至少需要多少个类二进制数字。例如：
  - 如果 n 中最大数字是 5，那么至少需要 5 个类二进制数字（每个类二进制数字的最大值为 1，如 1, 10, 100, 1000, 10000）。
  - 如果最大数字是 9，则需要至少 9 个类二进制数字。

总结：

时间复杂度：O(k)，其中 k 是数字 n 的长度。我们只需要遍历一次 n。
空间复杂度：O(1)，只使用常量的额外空间（除了输入字符串）。

补充

为什么最大位数字决定了我们所需的类二进制数字个数？

假设给定一个数字 n，它的各个数字可以通过多个类二进制数字加起来得到。我们观察到，如果数字 n 中某一位上的数字最大是 9（比如 9876543210），那么我们至少需要 9 个类二进制数字。

例子说明

考虑数字 n = 212：

212 -> 111 + 101

这表示 212 可以由两个类二进制数字组成：111 和 101。这样我们就用最少的两个类二进制数字表示了 212。

我们继续来分析更大的数字。例如，考虑 9876543210，它的每一位数字分别是：

9876543210 -> 9999999999 需要至少 9 个类二进制数字

这里的最大数字是 9，所以我们需要至少 9 个类二进制数字来组成这个数字。更直观地理解：

每个类二进制数字代表一种由 1 和 0 组成的组合（例如 1, 10, 100 等等），而每一位数字的值决定了我们需要几个这样的类二进制数字来填补对应的数字。

具体推理：

每个类二进制数字只能包含 1 和 0，比如 1, 10, 100, 111。
如果某一位的数字为 n，这意味着我们至少需要 n 个类二进制数字来填充这个位置的数字。例如：
- 如果某位为 5，我们至少需要 5 个类二进制数字才能表达这 5（例如 11111）。
- 如果某位为 9，我们至少需要 9 个类二进制数字来表示（例如 111111111）。