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原站题解
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