十-二进制数的最少数目
难度:
标签:
题目描述
代码结果
运行时间: 32 ms, 内存: 16.8 MB
/*
题目思路:
1. 给定的数字字符串 n 中,每一位数字表示这个位置的十进制数。
2. 我们需要找到和为 n 的最少的十-二进制数,这些数每位上只能是 0 或 1。
3. 实际上,我们可以发现每一位上的数字最大值决定了最少的十-二进制数数目,因为每一个十-二进制数的每一位最多是1,所以最大的那一位数字决定了我们需要多少个十-二进制数。
*/
import java.util.stream.*;
public class Solution {
public int minPartitions(String n) {
return n.chars() // 将字符串转换为字符流
.map(c -> c - '0') // 将每个字符转换为对应的数字
.max() // 找到最大值
.orElse(0); // 如果流为空,返回0(实际上不可能因为n.length >= 1)
}
}
解释
方法:
题解的核心思路是寻找给定数字字符串 n 中的最大数字字符。由于每个十-二进制数的数字只能是 0 或 1,因此要使若干个十-二进制数之和等于一个具体的十进制数,至少需要等于该十进制数中的最大数字的十-二进制数的数量。例如,如果 n 中的最大数字是 8,则至少需要 8 个十-二进制数相加,以保证它们的和能覆盖每个位置上的数值,这是因为每个十-二进制数的每位数字只能为 0 或 1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中为什么不需要考虑每个数字具体的位置,而只关注出现过的最大数字?
▷🦆
题解中提到,扫描数字直到找到最大的数字为止,是否意味着在找到最大数字后,其他较小数字的检查是多余的?
▷🦆
在这种算法中,是否考虑过在字符串n过长时的效率问题,比如超过100000位的情况?
▷🦆
如果字符串n中包含了从0到9的每一个数字,算法是否仍然有效,尤其是在n非常长时?
▷