LeetCode 1012. 至少有 1 位重复的数字
原题链接
困难
作者:
大风大雪
,
2023-11-14 16:08:55
,
所有人可见
,
阅读 45
数位DP 文字版
class Solution {
public:
int numDupDigitsAtMostN(int n) {
auto s = to_string(n);
int m = s.length(), memo[m][1 << 10];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int, int, bool, bool)> dfs = [&](int i, int mask, bool is_limit, bool is_num) -> int {
if (i == m)
// 前面没有填数 不能为一个数字
return is_num; // is_num 为 true 表示得到了一个合法数字
// 前面填的数字不是最高位 后面随意填 重复了
// 例如 前面最高位是6 但是填了0-5 后面随意填
// 算0时和算5时 后面随意填 重复了
if (!is_limit && is_num && memo[i][mask] != -1)
return memo[i][mask];
int res = 0;
// 前面不填 现在也可以不填
if (!is_num) // 可以跳过当前数位
// 当前位不填 下一位没有限制 且前面没有填数
res += dfs(i + 1, mask, false, false);
int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 n 的一样,那么这一位至多填数字 s[i](否则就超过 n 啦)
for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
// d 不在 mask 中
if ((mask >> d & 1) == 0) {
// is_limit 判断最高位是否是9
// is_limit && d == up 有限制 且最高位等于当前位
res += dfs(i + 1, mask | (1 << d), is_limit && d == up, true);
}
// 前面填的数字不是最高位 后面随意填 重复了
// 例如 前面最高位是6 但是填了0-5 后面随意填
// 算0时和算5时 后面随意填 重复了
if (!is_limit && is_num)
memo[i][mask] = res;
return res;
};
// 不能超过n 当前位有限制 前面没有填数
return n - dfs(0, 0, true, false);
}
};