Leetcode 3272. Find the Count of Good Integers

本文主要是介绍Leetcode 3272. Find the Count of Good Integers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 3272. Find the Count of Good Integers
- 1. 解题思路
- 2. 代码实现

题目链接：3272. Find the Count of Good Integers

1. 解题思路

这一题我思路上是比较暴力的，就是典型地分步骤执行：

找出所有的可能构成回文的长度为n的字符组合
对于任意字符组合，判断其是否可以构成一个被k整除的回文序列
考察这个字符组合可以构成的非零开头的数字个数

其中，对于第一步，我们可以采用一个动态规划的方式进行实现，分别考察从0到9各自取用多少个元素，使之满足总长度为n，且至多只有一个元素的个数为奇数个。

然后，对于第二个，我们倒是没有什么太好的办法，只能暴力地遍历所有可能的回文，判断其是否存在某个元素满足能够被k整除。不过我们倒是可以稍微做一些简化：

如果总长度为1，那么只需要判断一下这个元素是否能被k整除即可
如果非零元素的个数至多只有1个，且要求总长度不小于2，那么可以直接干掉
如果 $k = 3$ 或者 $k = 9$ ，那么只需要判断所有元素的和是否能被 $k$ 整除即可
如果 $k = 5$ ，那么只需要判断是否存在至少两个 $5$ 即可。

而最后，对于第三步，这就是一个简单的排列组合的题目，字符总长为 $n$ ，假设任意数字 $i$ 的数目为 $n_i$ ，那么能够组成的所有非零开头的数字个数即为：
$\frac{(n-n_0) \times (n-1)!}{\mathop{\Pi}\limits_{i=0}^{9} n_i!}$

2. 代码实现

我们给出最终的python代码实现如下：

@lru_cache(None)
def is_valid(sub):if sub == "":return Truecnt = Counter(sub)s = [v%2 for v in cnt.values()]return sum(s) <= 1@lru_cache(None)
def dp(idx, remain):if remain == 0:return [""]elif idx == 9:return ["9" * remain]ans = []for i in range(remain+1):subs = [str(idx) * i + sub for sub in dp(idx+1, remain-i)]subs = [sub for sub in subs if is_valid(sub)]ans += subsreturn ans@lru_cache(None)
def is_possible_devide_by_k(sub, k):if len(sub) == 1:return int(sub) % k == 0 and sub != "0"if Counter(sub)["0"] >= len(sub)-1:return Falseif k == 1:return Trueif k == 3 or k == 9:return sum(int(ch) for ch in sub) % k == 0if k == 5:return Counter(sub)["5"] > 1cnt = Counter(sub)pair = "".join(ch * (v//2) for ch, v in cnt.items())unique = [ch for ch, v in cnt.items() if v % 2 == 1]unique = unique[0] if len(unique) > 0 else ""return any(int("".join(sub) + unique + "".join(sub[::-1])) % k == 0 for sub in permutations(pair) if not ("".join(sub) + unique + "".join(sub[::-1])).startswith("0"))@lru_cache(None)
def count_fn(sub, k):ans = 0if is_possible_devide_by_k(sub, k):n = len(sub)cnt = Counter(sub)c = (n-cnt["0"]) * math.factorial(n-1)for v in cnt.values():c = c // math.factorial(v)ans += creturn ansclass Solution:def countGoodIntegers(self, n: int, k: int) -> int:all_possible_substrings = dp(0, n)return sum(count_fn(sub, k) for sub in all_possible_substrings)