范围内的数字计数
难度:
标签:
题目描述
代码结果
运行时间: 29 ms, 内存: 16.1 MB
/*
* 思路:
* 使用Java Stream API来实现相同的逻辑。
* 我们可以使用IntStream.rangeClosed生成一个范围内的所有整数,
* 并且通过filter和map来统计包含digit的次数。
*/
import java.util.stream.IntStream;
public class Solution {
public int digitsCount(int d, int low, int high) {
return IntStream.rangeClosed(low, high)
.mapToObj(String::valueOf)
.mapToInt(s -> (int) s.chars().filter(ch -> ch == ('0' + d)).count())
.sum();
}
}
解释
方法:
这道题使用数位DP来解决。主要思路是通过计算0到high之间数字d出现的次数,然后减去0到low-1之间数字d出现的次数,得到最终结果。通过迭代每一位数字,统计当前数位之前的数字中d出现的次数,并根据当前数位的值更新计数。使用pre数组记录之前的计数结果,cur数组更新当前位的计数。
时间复杂度:
O(n^2),其中n为high的位数。
空间复杂度:
O(n),其中n为high的位数。
代码细节讲解
🦆
题解中提到的数位DP(Dynamic Programming)具体是如何应用于这道题目的?能详细解释其工作原理吗?
▷🦆
为什么在计算过程中需要将数字递增1(num += 1)?这样做的目的和影响是什么?
▷🦆
在函数`count_digit`中,数组`cur`和`pre`的作用分别是什么?为什么需要两个数组进行迭代更新?
▷🦆
在`count_digit`函数的循环中,表达式`cur[c + int(w == d)] += 1`具体是如何更新当前位计数的?这里的逻辑能详细说明吗?
▷