力扣3272.统计好整数的数目
力扣3272.统计好整数的数目
-
贪心
-
枚举所有回文数，再找不重复的排列组合
-
因为是个回文数，所有只找左半边即可
-
-
最终排列组合的个数为上式
-
-
class Solution {public:long long countGoodIntegers(int n, int k) {vector<long long> fac(n+1);fac[0] = 1;//求阶乘for(int i=1;i<=n;i++)fac[i] = fac[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());//stoll将string转为longlongif(stoll(s) % k)continue;ranges::sort(s);//遍历过if(!vis.insert(s).second)continue;int cnt[10]{};//记录每个数字出现次数for(char c:s)cnt[c-'0'] ++;//全排列，还要去重复long long res = (n-cnt[0])*fac[n-1];//去重复for(int c:cnt)res /= fac[c];ans += res;}return ans;}};