难度: Hard
Submission
运行时间: 29 ms
内存: 16.1 MB
def count_digit(num, d):
# Calculate the number of occurrences of digit d within 1 to num by iteration
num += 1
lst = [int(x) for x in str(num)]
n = len(lst)
pre = [0] * (n + 1)
c = 0
zero = 0
xx = 1
for i in range(n):
cur = [0] * (n + 1)
for x in range(i + 1):
cur[x] += 9*pre[x]
cur[x+1] += pre[x]
# for w in range(10):
# cur[x + int(w == d)] += pre[x]
for w in range(lst[i]):
cur[c + int(w == d)] += 1
c += int(lst[i] == d)
pre = cur[:]
zero += xx
xx *= 10
ans = sum(pre[i] * i for i in range(n + 1))
return ans if d else ans - zero
class Solution:
def digitsCount(self, d: int, low: int, high: int) -> int:
# 模板：计算区间计数，使用右端点减去左端点，数位DP容斥模板题
return count_digit(high, d) - count_digit(low - 1, d)
Explain
这道题使用数位DP来解决。主要思路是通过计算0到high之间数字d出现的次数，然后减去0到low-1之间数字d出现的次数，得到最终结果。通过迭代每一位数字，统计当前数位之前的数字中d出现的次数，并根据当前数位的值更新计数。使用pre数组记录之前的计数结果，cur数组更新当前位的计数。
时间复杂度: O(n^2)，其中n为high的位数。
空间复杂度: O(n)，其中n为high的位数。
def count_digit(num, d):
# 计算1到num范围内数字d出现的次数，通过迭代每一位数字
num += 1
lst = [int(x) for x in str(num)]
n = len(lst)
pre = [0] * (n + 1) # 记录之前的计数结果
c = 0
zero = 0
xx = 1
for i in range(n):
cur = [0] * (n + 1) # 更新当前位的计数
for x in range(i + 1):
cur[x] += 9*pre[x] # 当前位为0~9时，前面数位中d出现的次数
cur[x+1] += pre[x] # 当前位为d时，前面数位中d出现的次数
for w in range(lst[i]):
cur[c + int(w == d)] += 1 # 更新当前位的计数
c += int(lst[i] == d) # 更新当前数字中d出现的次数
pre = cur[:]
zero += xx
xx *= 10
ans = sum(pre[i] * i for i in range(n + 1)) # 计算最终结果
return ans if d else ans - zero
class Solution:
def digitsCount(self, d: int, low: int, high: int) -> int:
# 模板：计算区间计数，使用右端点减去左端点，数位DP容斥模板题
return count_digit(high, d) - count_digit(low - 1, d)
Explore
数位DP是一种处理与数字的各个数位相关的问题的动态规划技术。在这个问题中，数位DP被用于计算一个数字范围内特定数字出现的次数。工作原理是：首先将数字逐位分解，并从最高位到最低位逐步计算每位数字d的出现次数。使用两个数组，pre和cur，来分别存储之前计算的结果和当前计算的结果。迭代每一位数字，更新cur数组，这样可以逐步构建出从最高位到当前位的所有可能性，并计算每种情况下数字d的出现次数。最终，通过累加这些计数来得到最终答案。
在计算过程中将数字递增1（num += 1）是为了将问题从计算从1到num的范围转换为计算0到num的范围，这样做简化了计算逻辑，因为包括0在内的计算可以使得边界处理变得更简单。例如，计算到999的情况可以直接处理为计算到1000，这样每一位的处理都是完整的，而不需要考虑边界位不完全的情况。
在函数`count_digit`中，`pre`数组用于存储之前计算的结果，即在考虑前i-1位时，每种数位的出现次数。`cur`数组则用于在考虑第i位时更新这些计数。使用两个数组进行迭代更新是因为我们需要基于之前的计数结果来计算当前数位带来的变化，而直接在`pre`上修改会破坏掉我们基于之前数位的计算结果。因此，通过`cur`存储新的结果，每完成一位的计算后，我们将`cur`的计算结果复制回`pre`，为下一位的计算做准备。
这个表达式是在处理当前位为具体值w（遍历前当前位可能的值）时，如何计数。`c` 是目前为止（不包括当前位）已经出现的d的次数，`int(w == d)` 是一个布尔表达式，当当前位的数字w等于d时为1，否则为0。因此，`c + int(w == d)` 表示在当前位数字为w时，从最高位到当前位的数字中d出现的总次数。表达式`cur[c + int(w == d)] += 1`意味着，在已有的数字情况下，增加一种新的计数情况，即在这种特定的数字构成下，数字d出现的总次数增加了1。