What is the pattern to solve the "Find the Count of Good Integers" problem?

The pattern involves using hash tables to track digit frequencies and applying mathematical combinatorics to validate k-palindromic number formations.

How does combinatorics help in solving this problem?

Combinatorics helps by calculating possible rearrangements of digits to form valid k-palindromic numbers, ensuring an efficient solution without brute force.

What are the constraints for the "Find the Count of Good Integers" problem?

The constraints are 1 <= n <= 10 and 1 <= k <= 9, allowing for efficient solutions without needing excessive computational resources.

How do hash tables assist in solving this problem?

Hash tables store the frequency of each digit, enabling fast lookup and counting, which is essential for identifying valid good integers.

What are common mistakes to avoid in this problem?

Common mistakes include not optimizing the use of hash tables, missing combinatorial logic for checking k-palindromic numbers, and attempting brute-force solutions without considering constraints.

#3272

Hard

auto_awesome哈希·数学

LeetCode 题解工作台

统计好整数的数目

给你两个正整数 n 和 k 。如果一个整数 x 满足以下条件，那么它被称为 k 回文整数。 x 是一个回文整数。 x 能被 k 整除。如果一个整数的数位重新排列后能得到一个 k 回文整数，那么我们称这个整数为好整数。比方说， k = 2 ，那么 2020 可以重新排列得到 20…

哈希表数学组合数学枚举

题目描述

给你两个正整数 n 和 k 。

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

x 是一个回文整数。
x 能被 k 整除。

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

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

注意，任何整数在重新排列数位之前或者之后 都不能 有前导 0 。比方说 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

lightbulb

解题思路

方法一：枚举 + 组合数学

我们可以考虑枚举所有长度为 $n$ 的回文数，判断它们是否是 $k$ 回文数。由于回文数的性质，我们只需要枚举前半部分的数字，然后将其反转拼接到后面即可。

前半部分的数字长度为 $\lfloor \frac{n - 1}{2} \rfloor$ ，那么前半部分的数字范围是 $[10^{\lfloor \frac{n - 1}{2} \rfloor}, 10^{\lfloor \frac{n - 1}{2} \rfloor + 1})$ 。我们可以将前半部分的数字拼接到后面，形成一个长度为 $n$ 的回文数。注意到，如果 $n$ 是奇数，则需要将中间的数字做特殊处理。

然后，我们判断该回文数是否是 $k$ 回文数，如果是，则统计该回文数的所有排列组合。为了避免重复，我们可以使用一个集合 $\textit{vis}$ 来存储已经出现过的回文数的每个最小排列。如果该回文数的最小排列已经出现过，则跳过该回文数。否则，我们统计该回文数有多少个不重复的排列组合，添加到答案中。

我们可以使用一个数组 $\textit{cnt}$ 来统计每个数字出现的次数，然后使用组合数学的公式计算排列组合的数量。具体来说，假设数字 $0$ 出现了 $x_0$ 次，数字 $1$ 出现了 $x_1$ 次，...，数字 $9$ 出现了 $x_9$ 次，那么该回文数的排列组合数量为：

\frac{(n - x_0) \cdot (n - 1)!}{x_0! \cdot x_1! \cdots x_9!}

其中 $(n - x_0)$ 表示最高位可以选择除 $0$ 以外的所有数字，而 $(n - 1)!$ 表示除最高位以外的所有数字的排列组合数量，然后我们除以每个数字出现的次数的阶乘，避免重复。

最后，我们将所有的排列组合数量相加，得到最终的答案。

时间复杂度 $({10}^m \times n \times \log n)$ ，空间复杂度 $O({10}^m \times n)$ ，其中 $m = \lfloor \frac{n - 1}{2} \rfloor$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def countGoodIntegers(self, n: int, k: int) -> int:
        fac = [factorial(i) for i in range(n + 1)]
        ans = 0
        vis = set()
        base = 10 ** ((n - 1) // 2)
        for i in range(base, base * 10):
            s = str(i)
            s += s[::-1][n % 2 :]
            if int(s) % k:
                continue
            t = "".join(sorted(s))
            if t in vis:
                continue
            vis.add(t)
            cnt = Counter(t)
            res = (n - cnt["0"]) * fac[n - 1]
            for x in cnt.values():
                res //= fac[x]
            ans += res
        return ans

speed

复杂度分析

指标	值
时间	O(n \log n \times 10^m)
空间	O(n \times 10^m)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate optimizes hash table usage for digit counting.
question_mark
Evaluate the candidate's approach to applying combinatorics in rearranging digits.
question_mark
Assess if the candidate can handle the constraints efficiently without brute force.

warning

常见陷阱

外企场景

error
Not efficiently handling the count of digits in the hash table, leading to unnecessary complexity.
error
Missing the importance of combinatorial logic in validating k-palindromic numbers.
error
Overlooking the constraints, attempting brute-force solutions for larger values of n or k.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Varying the size of n and k could introduce a need for different optimization strategies.
arrow_right_alt
Expanding the problem to allow for larger k values could affect the solution's performance.
arrow_right_alt
Testing with larger numbers or edge cases like n = 1 or k = 9 can challenge the solution's efficiency.

help

常见问题

外企场景

继续练习

#3312 查询排序后的最大公约数 #3395 唯一中间众数子序列 I #3404 统计特殊子序列的数目