力扣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转为longlong if(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; } };