LeetCode 3272.统计好整数的数目:枚举+排列组合+哈希表

发布于:2025-04-16 ⋅ 阅读:(25) ⋅ 点赞:(0)

【LetMeFly】3272.统计好整数的数目:枚举+排列组合+哈希表

力扣题目链接:https://leetcode.cn/problems/find-the-count-of-good-integers/

给你两个  整数 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

解题方法:枚举+排列组合+哈希表

我们可以枚举所有长度为 n n n的数字回文字符串。对于一个回文串,如果其对应整数能够被 k k k整除,则这个字符串的所有排列都能被 k k k整除。

问题就转化为了以下三个:

  1. 如何枚举所有长度为 n n n的数字回文串?

    我们可以枚举字符串的前半部分,然后反转得到后半部分并拼接,就得到了回文字符串。

    具体的,我们可以从 [ 1 0 ⌊ n − 1 2 ⌋ , 1 0 ⌊ n − 1 2 ⌋ + 1 ) [10^{\lfloor\frac{n-1}2\rfloor}, 10^{\lfloor\frac{n-1}2\rfloor+1}) [102n1,102n1+1)枚举前半字符串,若 n n n为奇数则包含中间位置元素。

  2. 一个“k回文整数字符串”有多少个排列?多少个字符串重新排列后能得到这个字符串?

    我们分别统计字符串中每个数字出现了多少次,假设字符串长度为 n n n

    首先计算第一位有多少种可能,第一位不能为 0 0 0,因此方案数为 n − t i m e s [ 0 ] n-times[0] ntimes[0]

    接着计算其他位,其他的 n − 1 n-1 n1个数字可以随便排列,其他位的方案数为 ( n − 1 ) ! (n-1)! (n1)!

    由于其中可能存在重复元素,例如 121 121 121中有两个 1 1 1,这两个 1 1 1谁在前谁在后无法区分,只能有一种方案,所以要除以 2 ! 2! 2!

    总的方案数为: ( n − t i m e s [ 0 ] ) × ( n − 1 ) ! Π i = 0 9 t i m e s [ i ] \frac{(n-times[0])\times (n-1)!}{\Pi_{i=0}^{9}times[i]} Πi=09times[i](ntimes[0])×(n1)!

  3. 如何保证每个排列不会被重复统计?

    假设我已经统计过 1221 1221 1221的所有全排列了,那么我遇到 2112 2112 2112时就不能再统计 2112 2112 2112的所有全排列了,因为 1221 1221 1221 2112 2112 2112的全排列时相同的。

    如何做到?其实我们只需要使用一个哈希表,记录字符串 s s s排序后的字符串是否出现过就好了。

时空复杂度分析

  • 时间复杂度 O ( 1 0 m × n log ⁡ n ) O(10^{m}\times n\log n) O(10m×nlogn),其中 m = ⌊ n − 1 2 ⌋ m=\lfloor\frac{n-1}2\rfloor m=2n1
  • 空间复杂度 O ( 1 0 m × n ) O(10^m\times n) O(10m×n)

AC代码

C++
/*
 * @Author: LetMeFly
 * @Date: 2025-04-12 07:51:15
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-04-12 09:25:01
 * @Description: AC,21.21%,93.94%
 */
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif

/*
1 -> 1-9
2 -> 1-9
3 -> 10->99
4 -> 10->99
5 -> 100->999
6 -> 100->999

n -> [10^((n-1)/2-1), 10^((n-1)/2)-1)
*/
typedef long long ll;

class Solution {
private:
    int k;
    unordered_set<string> visited;
    vector<int> factor;
    int times[10];

    void initFactor(int n) {
        factor.resize(n + 1);
        factor[0] = 1;
        for (int i = 1; i <= n; i++) {
            factor[i] = factor[i - 1] * i;
        }
    }

    bool ifVisited(string s) {
        sort(s.begin(), s.end());
        if (visited.count(s)) {
            return true;
        }
        visited.insert(s);
        return false;
    }
    
    bool isOk(string& s) {
        ll val = stoll(s);
        // printf("%s: %d\n", s.c_str(), val % k == 0);  // *****
        return val % k == 0;
    };

    ll calc(string& s) {
        memset(times, 0, sizeof(times));
        for (char c : s) {
            times[c - '0']++;
        }
        ll ans = (s.size() - times[0]) * factor[s.size() - 1];
        for (int i = 0; i < 10; i++) {
            ans /= factor[times[i]];
        }
        return ans;
    }
public:
    ll countGoodIntegers(int n, int k) {
        initFactor(n);
        this->k = k;
        ll ans = 0;
        for (int start = pow(10, (n - 1) / 2), end = start * 10; start < end; start++) {
            string prefix = to_string(start), suffix = prefix.substr(0, prefix.size() - n % 2);
            reverse(suffix.begin(), suffix.end());
            string thisNum = prefix + suffix;
            if (isOk(thisNum) && !ifVisited(thisNum)) {  // 注意ifVisited会将thisNum加入哈希表的话记得先判断isOk再判断ifVisited
                // printf("ans: %lld, calc(%s): %lld, ans = ans + calc(%s) = %lld\n", ans, thisNum.c_str(), calc(thisNum), thisNum.c_str(), ans + calc(thisNum));  // ****
                ans += calc(thisNum);
            }
        }
        return ans;
    }
};
Python
'''
Author: LetMeFly
Date: 2025-04-12 09:44:25
LastEditors: LetMeFly.xyz
LastEditTime: 2025-04-12 10:52:36
Description: 中间终中断了下
'''
from collections import Counter

class Solution:
    def isOk(self, s: str) -> bool:
        return int(s) % self.k == 0
    
    def ifVisited(self, s: str) -> bool:
        s = ''.join(sorted(s))
        if s in self.visited:
            return True
        self.visited.add(s)
        return False
    
    def calc(self, s: str) -> int:
        times = Counter(s)
        ans = (len(s) - times['0']) * self.factor[len(s) - 1]
        for _, val in times.items():
            ans //= self.factor[val]
        return ans

    def countGoodIntegers(self, n: int, k: int) -> int:
        self.k = k
        self.factor = [1] * (n + 1)
        for i in range(1, n + 1):
            self.factor[i] = self.factor[i - 1] * i
        self.visited = set()
        base = pow(10, (n - 1) // 2)
        ans = 0
        for i in range(base, base * 10):
            prefix = str(i)
            s = prefix + prefix[::-1][n % 2:]
            if self.isOk(s) and not self.ifVisited(s):
                ans += self.calc(s)
        return ans

Java
/*
 * @Author: LetMeFly
 * @Date: 2025-04-12 10:53:42
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-04-12 11:13:08
 */
import java.util.Set;
import java.util.HashSet;
// import java.lang.StringBuilder;  // 默认自动导入 无需手动导入
import java.util.Arrays;

class Solution {
    private int k;
    private int[] factor;
    private Set<String> visited = new HashSet<>();

    private boolean isOk(String s) {
        return Long.parseLong(s) % k == 0;
    }

    private boolean ifVisited(String s) {
        char[] array = s.toCharArray();
        Arrays.sort(array);
        String sorted = new String(array);
        return !visited.add(sorted);
    }

    private long calc(String s) {
        int[] times = new int[10];
        for (char c : s.toCharArray()) {
            times[c - '0']++;
        }
        long ans = (s.length() - times[0]) * factor[s.length() - 1];
        for (int i = 0; i < 10; i++) {
            ans /= factor[times[i]];
        }
        return ans;
    }

    public long countGoodIntegers(int n, int k) {
        this.k = k;
        factor = new int[n + 1];
        factor[0] = 1;
        for (int i = 1; i <= n; i++) {
            factor[i] = factor[i - 1] * i;
        }
        long ans = 0;
        for (int from = (int)Math.pow(10, (n - 1) / 2), to = from * 10; from < to; from++) {
            String prefix = String.valueOf(from);
            String suffix = new StringBuilder(prefix).reverse().substring(n % 2);
            String s = prefix + suffix;
            if (isOk(s) && !ifVisited(s)) {
                ans += calc(s);
            }
        }
        return ans;
    }
}

/*
API:

java 子字符串
反转字符串
整数转字符串
字符串拼接
字符串转整数
*/
Go
/*
 * @Author: LetMeFly
 * @Date: 2025-04-12 11:14:05
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-04-12 11:40:36
 * @Description: AC,25.00%,75.00%,一遍过
 */
package main

import (
    "math"
    "strconv"
    "sort"
    "strings"
)

type solution3273 struct{
    n, k int
    factor []int
    visited map[string]bool
}

func init3273(n int, k int) *solution3273 {
    ans := &solution3273{
        n: n,
        k: k,
        factor: make([]int, n + 1),
        visited : map[string]bool{},
    }
    ans.factor[0] = 1
    for i := 1; i <= n; i++ {
        ans.factor[i] = ans.factor[i - 1] * i
    }
    return ans
}

func (t* solution3273) isOk(s string) bool {
    val, _ := strconv.Atoi(s)
    return val % t.k == 0
}

func (t* solution3273) ifVisited(s string) bool {
    array := strings.Split(s, "")
    sort.Strings(array)
    s = strings.Join(array, "")
    if t.visited[s] {
        return true
    }
    t.visited[s] = true
    return false
}

func (t* solution3273) calc(s string) (ans int64) {
    times := [10]int{}
    for i, _ := range s {
        times[s[i] - '0']++
    }
    ans = int64(t.n - times[0]) * int64(t.factor[t.n - 1])
    for _, v := range times {
        ans /= int64(t.factor[v])
    }
    return
}

func (t* solution3273) getFullS(prefix string) string {
    suffix := []byte(prefix)
    if t.n % 2 == 1 {
        suffix = suffix[:len(suffix) - 1]
    }
    for i := 0; i < len(suffix) / 2; i++ {
        suffix[i], suffix[len(suffix) - i - 1] = suffix[len(suffix) - i - 1], suffix[i]
    }
    return prefix + string(suffix)
}

func countGoodIntegers(n int, k int) (ans int64) {
    solution := init3273(n, k)
    from := int(math.Pow10((n - 1) / 2))
    to := from * 10
    for i := from; i < to; i++ {
        s := solution.getFullS(strconv.Itoa(i))
        if solution.isOk(s) && !solution.ifVisited(s) {
            ans += solution.calc(s)
        }
    }
    return
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源