至少有 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 <= 10⁹

# 思路

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java