题目描述：
给出正整数 $ n $ ，返回在 $ [1,n] $ 中至少存在一个重复数字的正整数的个数。
数据范围：
$ 1\le n \le 10^9 $
题解：
数据范围非常大。考虑分数位考虑或者使用排列组合。
正着考虑该问题不容易，可以从问题的反面入手，使用 $ n $ 减去不存在重复数字的个数。
数位的话，先将数字 $ n $ 转为字符串，可以直接调用 to_string函数（c++11）。
然后使用dfs从最高位开始往低位搜索。枚举范围是 $ [0,upper] $ 。如果前一位step - 1取了 $ upper $ ，那么当前位 step 的 $ upper $ 等于字符串该位的值；否则的话等于 $ 9 $ 。
使用标志位 $ mask $ 记录使用了哪些数字，以免出现重复。使用了一个数字 $ i $ 之后，需要修改 $ mask $ ，mask = mask | (1 << i) 。需要注意如果 $ mask = 0 $ ，并且当前位置选的 $ i = 0 $ ，那么就不需要修改 $ mask $ ，否则的话会标记为 $ 1 $ 被使用了，出现错误。
将标志位置为 $ 1 $ ：mask | (1 << i)
将标志位置为 $ 0 $ ：mask & ~(1 << i)
同时需要记录前一位是不是取的 $ upper $ 。
这样的话使用了 step, s, isPreUpper, mask 四个状态量，就可以dfs搜索了。
考虑记忆化优化时间复杂度。
因为如果前一个位置不是 $ upper $ ，那么从当前位置往后的数量其实只与 $ mask $ 有关，所以可以考虑使用 $ (i, mask) $ 记忆化。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
int numDupDigitsAtMostN(int n)
{
string s = to_string(n);
return n - dfs(0, s, true, 0);
}
int dfs(int step, string &s, bool isPreUpper, int mask)
{
if (step == s.size())
{
return mask != 0;
}
int ans = 0;
int upper = isPreUpper ? (s[step] - '0') : 9;
for (int i = 0; i <= upper; ++i)
{
if (mask & (1 << i))
continue;
int new_mask = mask;
if (mask == 0 && i == 0)
new_mask = 0;
else
new_mask = mask | (1 << i);
ans += dfs(step + 1, s, isPreUpper && i == upper, new_mask);
}
return ans;
}
};
|
记忆化之后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<vector<int>> dp;
int numDupDigitsAtMostN(int n)
{
string s = to_string(n);
dp.resize(s.size(), vector<int>(1<<10, 0));
return n - dfs(0, s, true, 0) + 1;
}
int dfs(int step, string &s, bool isPreUpper, int mask)
{
if (step == s.size())
{
return 1;
}
if (!isPreUpper && dp[step][mask])
{
return dp[step][mask];
}
int ans = 0;
int upper = isPreUpper ? (s[step] - '0') : 9;
for (int i = 0; i <= upper; ++i)
{
if (mask & (1 << i))
continue;
int new_mask = mask;
if (mask == 0 && i == 0)
new_mask = 0;
else
new_mask = mask | (1 << i);
ans += dfs(step + 1, s, isPreUpper && i == upper, new_mask);
}
if (!isPreUpper)
{
dp[step][mask] = ans;
}
return ans;
}
};
|