leetcode
leetcode 901 ~ 950
范围内的数字计数

范围内的数字计数

难度:

标签:

题目描述

代码结果

运行时间: 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)具体是如何应用于这道题目的?能详细解释其工作原理吗?
数位DP是一种处理与数字的各个数位相关的问题的动态规划技术。在这个问题中,数位DP被用于计算一个数字范围内特定数字出现的次数。工作原理是:首先将数字逐位分解,并从最高位到最低位逐步计算每位数字d的出现次数。使用两个数组,pre和cur,来分别存储之前计算的结果和当前计算的结果。迭代每一位数字,更新cur数组,这样可以逐步构建出从最高位到当前位的所有可能性,并计算每种情况下数字d的出现次数。最终,通过累加这些计数来得到最终答案。
🦆
为什么在计算过程中需要将数字递增1(num += 1)?这样做的目的和影响是什么?
在计算过程中将数字递增1(num += 1)是为了将问题从计算从1到num的范围转换为计算0到num的范围,这样做简化了计算逻辑,因为包括0在内的计算可以使得边界处理变得更简单。例如,计算到999的情况可以直接处理为计算到1000,这样每一位的处理都是完整的,而不需要考虑边界位不完全的情况。
🦆
在函数`count_digit`中,数组`cur`和`pre`的作用分别是什么?为什么需要两个数组进行迭代更新?
在函数`count_digit`中,`pre`数组用于存储之前计算的结果,即在考虑前i-1位时,每种数位的出现次数。`cur`数组则用于在考虑第i位时更新这些计数。使用两个数组进行迭代更新是因为我们需要基于之前的计数结果来计算当前数位带来的变化,而直接在`pre`上修改会破坏掉我们基于之前数位的计算结果。因此,通过`cur`存储新的结果,每完成一位的计算后,我们将`cur`的计算结果复制回`pre`,为下一位的计算做准备。
🦆
在`count_digit`函数的循环中,表达式`cur[c + int(w == d)] += 1`具体是如何更新当前位计数的?这里的逻辑能详细说明吗?
这个表达式是在处理当前位为具体值w(遍历前当前位可能的值)时,如何计数。`c` 是目前为止(不包括当前位)已经出现的d的次数,`int(w == d)` 是一个布尔表达式,当当前位的数字w等于d时为1,否则为0。因此,`c + int(w == d)` 表示在当前位数字为w时,从最高位到当前位的数字中d出现的总次数。表达式`cur[c + int(w == d)] += 1`意味着,在已有的数字情况下,增加一种新的计数情况,即在这种特定的数字构成下,数字d出现的总次数增加了1。

相关问题

数字 1 的个数

给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

 

示例 1:

输入:n = 13
输出:6

示例 2:

输入:n = 0
输出:0

 

提示:

  • 0 <= n <= 109