class Solution {
public:
long long countGoodIntegers(int n, int k) {
}
};
3272. 统计好整数的数目
给你两个 正 整数 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
解释：
部分好整数如下：
示例 2：
输入：n = 1, k = 4
输出：2
解释：
两个好整数分别是 4 和 8 。
示例 3：
输入：n = 5, k = 6
输出：2468
提示：
1 <= n <= 101 <= k <= 9原站题解
rust 解法, 执行用时: 334 ms, 内存消耗: 3 MB, 提交时间: 2025-04-12 08:18:57
use std::collections::HashSet;
impl Solution {
pub fn count_good_integers(n: i32, k: i32) -> i64 {
let mut dict: HashSet<String> = HashSet::new();
let base = 10i32.pow(((n - 1) / 2) as u32);
let skip = (n & 1) as usize;
/* 枚举 n 个数位的回文数 */
for i in base..base * 10 {
let s = i.to_string();
let rev: String = s.chars().rev().skip(skip).collect();
let combined = format!("{}{}", s, rev);
let palindromicInteger: i64 = combined.parse().unwrap();
/* 如果当前回文数是 k 回文数 */
if palindromicInteger % (k as i64) == 0 {
let mut sorted_chars: Vec<char> = combined.chars().collect();
sorted_chars.sort();
dict.insert(sorted_chars.into_iter().collect());
}
}
let mut factorial = vec![1i64; (n + 1) as usize];
for i in 1..=n as usize {
factorial[i] = factorial[i - 1] * (i as i64);
}
let mut ans = 0i64;
for s in dict {
let mut cnt = vec![0; 10];
for c in s.chars() {
cnt[c.to_digit(10).unwrap() as usize] += 1;
}
/* 计算排列组合 */
let mut tot = (n as i64 - cnt[0] as i64) * factorial[(n - 1) as usize];
for &x in cnt.iter() {
tot /= factorial[x];
}
ans += tot;
}
ans
}
}
javascript 解法, 执行用时: 932 ms, 内存消耗: 76.2 MB, 提交时间: 2025-04-12 08:18:31
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var countGoodIntegers = function(n, k) {
const dict = new Set();
const base = Math.pow(10, Math.floor((n - 1) / 2));
const skip = n & 1;
/* 枚举 n 个数位的回文数 */
for (let i = base; i < base * 10; i++) {
let s = i.toString();
s += s.split('').reverse().slice(skip).join('');
const palindromicInteger = parseInt(s);
/* 如果当前回文数是 k 回文数 */
if (palindromicInteger % k === 0) {
const sortedS = s.split('').sort().join('');
dict.add(sortedS);
}
}
const factorial = Array(n + 1).fill(1n);
for (let i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * BigInt(i);
}
let ans = 0n;
for (const s of dict) {
const cnt = Array(10).fill(0);
for (const c of s) {
cnt[parseInt(c)]++;
}
/* 计算排列组合 */
let tot = BigInt(n - cnt[0]) * factorial[n - 1];
for (const x of cnt) {
tot /= factorial[x];
}
ans += tot;
}
return Number(ans);
};
golang 解法, 执行用时: 92 ms, 内存消耗: 9 MB, 提交时间: 2024-10-21 22:20:38
func countGoodIntegers(n, k int) (ans int64) {
factorial := make([]int, n+1)
factorial[0] = 1
for i := 1; i <= n; i++ {
factorial[i] = factorial[i-1] * i
}
vis := map[string]bool{}
base := int(math.Pow10((n - 1) / 2))
for i := base; i < base*10; i++ { // 枚举回文数左半边
x := i
t := i
if n%2 > 0 {
t /= 10
}
for ; t > 0; t /= 10 {
x = x*10 + t%10
}
if x%k > 0 { // 回文数不能被 k 整除
continue
}
bs := []byte(strconv.Itoa(x))
slices.Sort(bs)
s := string(bs)
if vis[s] { // 不能重复统计
continue
}
vis[s] = true
cnt := [10]int{}
for _, c := range bs {
cnt[c-'0']++
}
res := (n - cnt[0]) * factorial[n-1]
for _, c := range cnt {
res /= factorial[c]
}
ans += int64(res)
}
return
}
cpp 解法, 执行用时: 645 ms, 内存消耗: 18.7 MB, 提交时间: 2024-10-21 22:20:25
class Solution {
public:
long long countGoodIntegers(int n, int k) {
vector<int> factorial(n + 1);
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
}
long long ans = 0;
unordered_set<string> vis;
int base = pow(10, (n - 1) / 2);
for (int i = base; i < base * 10; i++) { // 枚举回文数左半边
string s = to_string(i);
s += string(s.rbegin() + (n % 2), s.rend());
if (stoll(s) % k) { // 回文数不能被 k 整除
continue;
}
ranges::sort(s);
if (!vis.insert(s).second) { // 不能重复统计
continue;
}
int cnt[10]{};
for (char c : s) {
cnt[c - '0']++;
}
int res = (n - cnt[0]) * factorial[n - 1];
for (int c : cnt) {
res /= factorial[c];
}
ans += res;
}
return ans;
}
};
java 解法, 执行用时: 433 ms, 内存消耗: 46.6 MB, 提交时间: 2024-10-21 22:20:11
class Solution {
public long countGoodIntegers(int n, int k) {
int[] factorial = new int[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
}
long ans = 0;
Set<String> vis = 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) { // 回文数不能被 k 整除
continue;
}
char[] sortedS = s.toCharArray();
Arrays.sort(sortedS);
if (!vis.add(new String(sortedS))) { // 不能重复统计
continue;
}
int[] cnt = new int[10];
for (char c : sortedS) {
cnt[c - '0']++;
}
int res = (n - cnt[0]) * factorial[n - 1];
for (int c : cnt) {
res /= factorial[c];
}
ans += res;
}
return ans;
}
}
python3 解法, 执行用时: 959 ms, 内存消耗: 17.7 MB, 提交时间: 2024-10-21 22:19:58
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: # 回文数不能被 k 整除
continue
sorted_s = ''.join(sorted(s))
if sorted_s in vis: # 不能重复统计
continue
vis.add(sorted_s)
cnt = Counter(sorted_s)
res = (n - cnt['0']) * fac[n - 1]
for c in cnt.values():
res //= fac[c]
ans += res
return ans