给定正整数 n,返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。
数据范围
1 <= n <= 1e9
class Solution {
public:
int f[11][1 << 11];
int m;
string s;
int dfs(int u, int mask, bool limit, bool is_num){
if(u == m) return is_num == true;
if(!limit && is_num && f[u][mask] != -1) return f[u][mask];
int res = 0;
if(!is_num)
res = dfs(u + 1, mask, false, false);
int up = limit ? s[u] - '0' : 9;
for(int i = 1 - (is_num == true); i <= up; i ++){
if(mask >> i & 1) continue;
res += dfs(u + 1, mask | (1 << i), (up == i) && limit, true);
}
if(!limit && is_num) f[u][mask] = res;
return res;
}
int numDupDigitsAtMostN(int n) {
memset(f, -1, sizeof f);
s = to_string(n);
m = s.size();
return n - dfs(0, 0, true, false);
}
};