数字 1 的个数
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 28 ms, 内存: 14.8 MB
/*
* 思路：
* 1. 使用 IntStream 生成从 1 到 num 的整数流。
* 2. 对每一个数字转换为字符串并检查其中的每个字符是否为 '1'。
* 3. 统计所有字符为 '1' 的出现次数。
*/
import java.util.stream.IntStream;
public class Solution {
public int countDigitOne(int num) {
return IntStream.rangeClosed(1, num)
.mapToObj(Integer::toString)
.flatMapToInt(CharSequence::chars)
.map(c -> c == '1' ? 1 : 0)
.sum();
}
}
解释
方法:
该题解使用了数位分析的方法来解决问题。算法通过逐个分析数字n的每一位来计算1的出现次数。首先，将整数n分解为三个部分：高位（high），当前位（cur），和低位（low）。'digit'代表当前分析位的数位值（1, 10, 100, ...）。算法从个位开始，逐步向高位移动，每次迭代更新三个部分的值：1. 如果当前位是0，则1的出现次数由更高位决定。2. 如果当前位是1，则1的出现次数由更高位和更低位共同决定。3. 如果当前位大于1，则1的出现次数也由更高位决定，但要加上当前数位值。这种逐位分析的方法避免了直接计数的大量重复操作，提高了效率。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
在数位分析方法中，你是如何确定将整数n分解为高位（high），当前位（cur），和低位（low）的，以及这种分解对于算法的意义何在？
▷🦆
题解中提到当当前位cur大于1时，结果会加上当前数位值digit，这里的逻辑依据是什么？为什么不只是高位的贡献乘以digit？
▷🦆
在更新低位low时，为什么要使用表达式`low += cur * digit`，这里的计算过程是怎样影响整个算法的计数逻辑的？
▷