广州西樵网站制作,哪个网站教做西餐,网站建设工作建议,政务网站建设总结Leetcode 2999. Count the Number of Powerful Integers 1. 解题思路2. 代码实现 题目链接#xff1a;10034. Count the Number of Powerful Integers
1. 解题思路
这一题的话其实还是一个典型的求不大于 N N N的特殊数字个数的问题。
这道题本质上进行一下替换还是要求如…Leetcode 2999. Count the Number of Powerful Integers 1. 解题思路2. 代码实现 题目链接10034. Count the Number of Powerful Integers
1. 解题思路
这一题的话其实还是一个典型的求不大于 N N N的特殊数字个数的问题。
这道题本质上进行一下替换还是要求如下问题 对于任意一个数 n n n求不大于 n n n的所有位数都不超过 l i m i t limit limit且最后几位数为 s s s的数的个数。 此时由于最后几位数以及被限制死了为 s s s于是我们只需要考虑 n n n的除了最后 s s s位之外的剩余部分不妨设为 m m m求其所有位都不超过 l i m i t limit limit的数的个数即 对于任意一个数 m m m求不大于 m m m的且所有位数都不超过 l i m i t limit limit的数的个数。 这个就是一个比较常规的题目了我们通过一个动态规划即可给出答案。
唯一需要注意的是需要考虑一下如果前面的位数恰好为 m m m时拼接上后置位 s s 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 (1max_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。
