Leetcode 2999. Count the Number of Powerful Integers

本文主要是介绍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$ 的，所有位数都不超过 $l imi t$ ，且最后几位数为 $s$ 的数的个数。

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

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

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

唯一需要注意的是，需要考虑一下如果前面的位数恰好为 $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)