[LeetCode] 每日一题 3272. 统计好整数的数目（困难题 枚举）

题目描述

给你两个 正 整数 n 和 k 。

如果一个整数 x 满足以下条件，那么它被称为 k 回文 整数 。

• x 是一个 回文整数 。

• x 能被 k 整除。

如果一个整数的数位重新排列后能得到一个 k 回文整数 ，那么我们称这个整数为 好 整数。比方说，k = 2 ，那么 2020 可以重新排列得到 2002 ，2002 是一个 k 回文串，所以 2020 是一个好整数。而 1010 无法重新排列数位得到一个 k 回文整数。

请你返回 n 个数位的整数中，有多少个 好 整数。

注意 ，任何整数在重新排列数位之前或者之后 都不能 有前导 0 。比方说 1010 不能重排列得到 101 。

回文数

如果一个整数向前和向后读都相同，则它是一个 回文数。 例如，121 是回文数，而 123 不是。

题目链接

https://leetcode.cn/problems/find-the-count-of-good-integers

示例输入

示例 1

输入：n = 3, k = 5

输出：27

解释：

部分好整数如下：

551 ，因为它可以重排列得到 515 。
525 ，因为它已经是一个 k 回文整数。

示例 2

输入：n = 1, k = 4

输出：2

解释：

两个好整数分别是 4 和 8 。

示例 3

输入：n = 5, k = 6

输出：2468

提示

• 1 <= n <= 10

• 1 <= k <= 9

解题思路

这题的核心在于枚举所有长度为 n 的 回文数，再判断这些回文数能否被 k 整除，并统计它们的所有 合法重排方式。

考虑到回文数的特点，只要知道左半部分（包括中间位），就可以唯一确定整个回文数。因此我们可以：

1. 设 m = (n - 1) // 2，枚举所有从 10^m 到 10^{m+1} - 1 之间的整数，作为回文数的左半边。

2. 生成完整的回文数 x（拼接左半边和其反转，注意奇偶长度的不同处理）。

3. 如果 x 能整除 k，再判断是否是一个 好整数。

好整数的判断要解决两个问题：

• 如何计算这个回文数所有可能重排的数量；

• 如何避免重复计算。

我们借鉴了「49. 字母异位词分组」的思路，使用一个哈希集合 visited 来记录排序后的字符串。如果某个字符串排序结果已出现过，说明它的所有排列已被统计过，直接跳过。

在组合数学部分，目标是计算一个含重复数字的全排列个数，需满足：

• 首位不能为0

• 除去重复元素带来的冗余（即除以相同数字的阶乘）

具体来说：

• 首位可以选的数字有 n - cnt[0] 种（去掉前导零情况）

• 其余 n - 1 位可以任意排列，共有 (n-1)! 种方式

• 对每个出现次数为 cnt[i] 的数字，需除以 cnt[i]! 来去重

最终累加所有合法情况，即为答案。

代码实现

class Solution {
    public long countGoodIntegers(int n, int k) {
        int[] fac = new int[n + 1];
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i;
        }
        long ans = 0;
        HashSet<String> visited = new HashSet<>();
        int base = (int)Math.pow(10, (n - 1) / 2);
        for (int i = base; i < base * 10; i++) {
            String s = Integer.toString(i);
            s += new StringBuilder(s).reverse().substring(n % 2);
            if (Long.parseLong(s) % k > 0) {
                continue;
            }
            char[] sortedS = s.toCharArray();
            Arrays.sort(sortedS);
            if (!visited.add(new String(sortedS))) {
                continue;
            }
            int[] cnt = new int[10];
            for (char c : sortedS) {
                cnt[c - '0']++;
            }
            int res = (n - cnt[0]) * fac[n - 1];
            for (int c : cnt) {
                res /= fac[c];
            }
            ans += res;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：
  枚举的回文数数量为约 9 * 10^{n/2 - 1}，每个回文数最多执行一次排列统计和哈希判断。整体时间复杂度近似为 O(10^{n/2} * n)。其中 n 来自字符串处理与阶乘组合计算

• 空间复杂度：
  主要来自哈希集合 visited 和计数字符数组，复杂度为 O(10^{n/2})

🧠这题虽然在枚举过程中看似暴力，但通过构造和剪枝，我们有效地避免了冗余计算，适当利用了回文数的对称性与组合数学技巧

总结

这题一开始确实有些绕，我也是在参考了别人的方法之后才逐步理清思路。关键在于：不直接枚举所有数字，而是先枚举合法的回文数，再进行去重和排列统计，借助哈希和组合数学，最终顺利解决。

如果你也被回文+排列+组合绕晕了，建议按步骤来理解这几个知识点的衔接，很多复杂题都是这样拆解后才显得“有章可循”。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。