Leetcode 2999. Count the Number of Powerful Integers_numberofpowerfulint

• 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 1
        elif 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 ans
    
    def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
        
        if any(int(bit) > limit for bit in s):
            return 0
        
        def count_powerful(n):
            ns = str(n)
            m = len(s)
            if len(ns) < m or ns < s.rjust(len(ns), "0"):
                return 0
            ans = -1 if ns[:-m] + s > ns and all(int(d) <= limit for d in ns[:-m]) else 0
            return ans + self.count(ns[:-m], limit)

        return count_powerful(finish) - count_powerful(start-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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