至少有 1 位重复的数字Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。
示例 1：
输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：
输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：
输入：n = 1000
输出：262
提示：
- 1 <= n <= 109
# 思路
dp数组
# 解法
class Solution {
public int numDupDigitsAtMostN(int n) {
String s = String.valueOf(n);
char[] chs = s.toCharArray();
int len = chs.length, c = 1, m = 0;
if (len == 1) return 0;
int[] dp = new int[len];
for (int i = 1; i < len; i++) {
dp[i] = (int) Math.pow(10, i) - (c = (10 - len + i) * c);
}
c = 9;
int c0 = 9;
for (int i = 1; i < len-1; i++) {
m += ((c0=c0*10) - (c=c*(10 - i)));
}
int f = 0;
for (int i = 0; i < len; i++) {
int t = chs[i] - '0', k = 0;
for (int j = 0; j < t; j++) {
if ((f & (1 << j)) == 0) k++;
}
m += ((t - k)*(int) Math.pow(10, len - i - 1));
if (i == 0) k--;
m += (dp[len - i - 1] * k);
if ((f & (1 << t)) != 0) return m + (i+1 < len ? Integer.parseInt(s.substring(i+1)) : 0) + 1;
f |= (1 << t);
}
return m;
}
}
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
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
# 总结
- 分析出几种情况，然后分别对各个情况实现
