Hard

题目描述

给你两个正整数 n 和 k。

如果一个整数 x 满足以下条件，则称其为 k-回文整数：

  • x 是回文数
  • x 能被 k 整除

如果一个整数的各位数字可以重新排列形成一个 k-回文整数，则称该整数为好整数。例如，当 k = 2 时，2020 可以重新排列为 k-回文整数 2002，而 1010 无法重新排列形成 k-回文整数。

返回包含 n 位数字的好整数的数量。

注意，任何整数在重新排列前后都不能有前导零。例如，1010 不能重新排列为 101。

示例 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

解题思路

这是一道涉及回文数、排列组合和数论的复杂题目。

核心思路是：一个数字是"好整数"当且仅当它的数字可以重新排列形成一个能被k整除的回文数。我们需要：

  1. 生成所有可能的k-回文数：枚举所有n位的回文数，筛选出能被k整除的
  2. 统计数字频率：对于每个k-回文数，统计各数字的出现频次
  3. 计算排列数：对于每种数字频次组合，计算有多少种不同的排列（避免前导零）
  4. 去重：相同数字频次组合只计算一次

关键观察：

  • 回文数只需要确定前半部分，后半部分可以镜像得到
  • 对于n位回文数，只需要枚举前⌈n/2⌉位数字
  • 使用多重集合排列公式计算排列数：n!/(n₁!×n₂!×…×nₖ!)
  • 需要特别处理前导零的情况

算法步骤：

  1. 生成所有n位的k-回文数的数字频次模式
  2. 对每种频次模式，计算对应的排列数（排除前导零）
  3. 累加所有排列数得到最终答案

代码实现

class Solution {
private:
    long long factorial[11];
    
    void precompute() {
        factorial[0] = 1;
        for (int i = 1; i <= 10; i++) {
            factorial[i] = factorial[i-1] * i;
        }
    }
    
    long long countPermutations(vector<int>& freq, int n) {
        long long total = factorial[n];
        for (int i = 0; i < 10; i++) {
            total /= factorial[freq[i]];
        }
        
        if (freq[0] == 0) return total;
        
        long long withLeadingZero = factorial[n-1];
        freq[0]--;
        for (int i = 0; i < 10; i++) {
            withLeadingZero /= factorial[freq[i]];
        }
        freq[0]++;
        
        return total - withLeadingZero;
    }
    
public:
    long long countGoodIntegers(int n, int k) {
        precompute();
        set<vector<int>> uniqueFreqs;
        
        int half = (n + 1) / 2;
        int start = 1;
        for (int i = 1; i < half; i++) start *= 10;
        int end = start * 10;
        
        for (int i = start; i < end; i++) {
            string s = to_string(i);
            string palindrome = s;
            for (int j = n % 2 == 0 ? half - 1 : half - 2; j >= 0; j--) {
                palindrome += s[j];
            }
            
            long long num = 0;
            for (char c : palindrome) {
                num = num * 10 + (c - '0');
            }
            
            if (num % k == 0) {
                vector<int> freq(10, 0);
                for (char c : palindrome) {
                    freq[c - '0']++;
                }
                uniqueFreqs.insert(freq);
            }
        }
        
        long long result = 0;
        for (auto& freq : uniqueFreqs) {
            vector<int> f = freq;
            result += countPermutations(f, n);
        }
        
        return result;
    }
};

class Solution:
    def countGoodIntegers(self, n: int, k: int) -> int:
        from math import factorial
        from collections import defaultdict
        
        def count_permutations(freq, n):
            total = factorial(n)
            for count in freq.values():
                total //= factorial(count)
            
            if freq[0] == 0:
                return total
            
            # 排除前导零的情况
            without_leading_zero = factorial(n - 1)
            freq[0] -= 1
            for count in freq.values():
                without_leading_zero //= factorial(count)
            freq[0] += 1
            
            return total - without_leading_zero
        
        unique_freqs = set()
        half = (n + 1) // 2
        
        # 生成回文数的前半部分
        start = 10**(half - 1)
        end = 10**half
        
        for i in range(start, end):
            s = str(i)
            # 构造回文数
            if n % 2 == 0:
                palindrome = s + s[::-1]
            else:
                palindrome = s + s[-2::-1]
            
            num = int(palindrome)
            if num % k == 0:
                freq = defaultdict(int)
                for digit in palindrome:
                    freq[int(digit)] += 1
                
                # 转换为tuple以便加入set
                freq_tuple = tuple(freq[i] for i in range(10))
                unique_freqs.add(freq_tuple)
        
        result = 0
        for freq_tuple in unique_freqs:
            freq = {i: freq_tuple[i] for i in range(10)}
            result += count_permutations(freq, n)
        
        return result

public class Solution {
    private long[] factorial = new long[11];
    
    private void Precompute() {
        factorial[0] = 1;
        for (int i = 1; i <= 10; i++) {
            factorial[i] = factorial[i-1] * i;
        }
    }
    
    private long CountPermutations(int[] freq, int n) {
        long total = factorial[n];
        for (int i = 0; i < 10; i++) {
            total /= factorial[freq[i]];
        }
        
        if (freq[0] == 0) return total;
        
        long withLeadingZero = factorial[n-1];
        freq[0]--;
        for (int i = 0; i < 10; i++) {
            withLeadingZero /= factorial[freq[i]];
        }
        freq[0]++;
        
        return total - withLeadingZero;
    }
    
    public long CountGoodIntegers(int n, int k) {
        Precompute();
        var uniqueFreqs = new HashSet<string>();
        
        int half = (n + 1) / 2;
        int start = (int)Math.Pow(10, half - 1);
        int end = (int)Math.Pow(10, half);
        
        for (int i = start; i < end; i++) {
            string s = i.ToString();
            string palindrome = s;
            
            if (n % 2 == 0) {
                palindrome += new string(s.Reverse().ToArray());
            } else {
                palindrome += new string(s.Take(s.Length - 1).Reverse().ToArray());
            }
            
            long num = long.Parse(palindrome);
            if (num % k == 0) {
                int[] freq = new int[10];
                foreach (char c in palindrome) {
                    freq[c - '0']++;
                }
                
                string freqStr = string.Join(",", freq);
                uniqueFreqs.Add(freqStr);
            }
        }
        
        long result = 0;
        foreach (string freqStr in uniqueFreqs) {
            int[] freq = freqStr.Split(',').Select(int.Parse).ToArray();
            result += CountPermutations((int[])freq.Clone(), n);
        }
        
        return result;
    }
}

var countGoodIntegers = function(n, k) {
    const factorial = [1];
    for (let i = 1; i <= 10; i++) {
        factorial[i] = factorial[i-1] * i;
    }
    
    function countPermutations(freq, n) {
        let total = factorial[n];
        for (let i = 0; i < 10; i++) {
            total /= factorial[freq[i]];
        }
        
        if (freq[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(10^(⌈n/2⌉) × n)
空间复杂度O(10^(⌈n/2⌉))

时间复杂度说明：需要枚举所有前半部分的可能数字组合（10^(⌈n/2⌉)），每次构造回文数和计算排列数需要O(n)时间。

空间复杂度说明：主要用于存储所有不同的数字频次组合，最多有10^(⌈n/2⌉)种。

相关题目