2出现的次数
难度:
标签:
题目描述
Write a method to count the number of 2s that appear in all the numbers between 0 and n (inclusive).
Example:
Input: 25 Output: 9 Explanation: (2, 12, 20, 21, 22, 23, 24, 25)(Note that 22 counts for two 2s.)
Note:
n <= 10^9
代码结果
运行时间: 27 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 使用 IntStream 生成从 0 到 n 的范围。
* 2. 将每个数字转换为字符串，并计算每个字符串中 '2' 出现的次数。
* 3. 使用 sum() 方法累加所有次数。
*/
import java.util.stream.IntStream;
public class CountTwosStream {
public static int countTwos(int n) {
return IntStream.rangeClosed(0, n)
.mapToObj(Integer::toString)
.flatMapToInt(num -> num.chars().map(c -> c == '2' ? 1 : 0))
.sum();
}
public static void main(String[] args) {
int n = 25;
System.out.println(countTwos(n)); // 输出：9
}
}
解释
方法:
这个题解采用了数位分析的方法来统计数字2的出现次数。首先，对于给定的数字n，算法逐位考察（从个位开始到最高位），并计算每一位上数字2出现的总次数。具体来说，对于每一位，算法分别计算这一位上的数字（curr）、其低位组成的数字（low）和高位组成的数字（high）。然后根据当前位的数字分三种情况处理：1) 当前位数字小于2时，2的数量由高位数字决定；2) 当前位数字等于2时，2的数量由高位和低位共同决定；3) 当前位数字大于2时，高位数字增加一的情况也需要计入2的总数。这种方法利用数学分割和模运算来避免直接的枚举，从而提高效率。
时间复杂度:
O(log(n))
空间复杂度:
O(1)
代码细节讲解
🦆
在处理数位时，算法是如何确保从个位开始逐位向高位处理的？
▷🦆
如果当前位的数字等于2，为什么在计算2的出现次数时需要将低位数字加1？
▷🦆
算法中的factor变量有什么作用，它是如何帮助确定当前处理的是哪一位数字的？
▷