Leetcode 2999. Count the Number of Powerful Integers

• Leetcode 2999. Count the Number of Powerful Integers
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：10034. Count the Number of Powerful Integers

1. 解题思路

这一题的话其实还是一个典型的求不大于$N$的特殊数字个数的问题。

这道题本质上进行一下替换还是要求如下问题：

对于任意一个数$n$，求不大于$n$的，所有位数都不超过$limit$，且最后几位数为$s$的数的个数。

此时，由于最后几位数以及被限制死了为$s$，于是我们只需要考虑$n$的除了最后$s$位之外的剩余部分（不妨设为$m$），求其所有位都不超过$limit$的数的个数，即：

对于任意一个数$m$，求不大于$m$的，且所有位数都不超过$limit$的数的个数。

这个就是一个比较常规的题目了，我们通过一个动态规划即可给出答案。

唯一需要注意的是，需要考虑一下如果前面的位数恰好为$m$时，拼接上后置位$s$是否是一个满足条件的答案，这个情况可能会给结果带来一个1的偏差，需要额外讨论一下。

2. 代码实现

给出python代码实现如下：

class Solution:@lru_cache(None)def count(self, n, max_bit):if len(n) == 0:return 1elif len(n) == 1:return 1 + min(int(n), max_bit)d = int(n[0])if d > max_bit:ans =  (1+max_bit) * self.count("9" * (len(n)-1), max_bit)else:ans = d * self.count("9" * (len(n)-1), max_bit) + self.count(n[1:], max_bit)return ansdef numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:if any(int(bit) > limit for bit in s):return 0def count_powerful(n):ns = str(n)m = len(s)if len(ns) < m or ns < s.rjust(len(ns), "0"):return 0ans = -1 if ns[:-m] + s > ns and all(int(d) <= limit for d in ns[:-m]) else 0return ans + self.count(ns[:-m], limit)return count_powerful(finish) - count_powerful(start-1)

提交代码评测得到：耗时45ms，占用内存20.6MB。