1015. Numbers With Repeated Digi

这是昨晚(3.16,2019）的一道周赛道。
我当时没有写出来。花了一个小时也没写出来。
后来看别人的答案，发现我的思路已经非常close了，就差最后一步要加HashSet判断去重的地方卡了，当时刚刚发现有这么一个问题， 没想起来怎么去重。

这题思路是这样的。
首先处理一下位数小于N的数，比如N = 3456,先算一下1位数的， 再算一下2位数的，再算一下 3位数的。
最后我们看从1000 to 3456有多少个。
找有重复的数字，就相当于找出那些没有重复的数字再从N里面减去就好了。
求没有重复的数字就相当于找一个组合。
对于3456,我们先找在1000 到2999之间的，再找3000到3399之间的，再找3400 to 3449之间的
再找3450 到3456之前的。
扫描前缀的不同长度， 1000 到 2999 是前缀为0的，第一位只能是1或者2,第二位可以有9种选择，第三位有8种选择，第四位有7种选择。
找3000 到3399之间时，注意后面的数字不能选3了，这时把上面的一位放到hashset里面去重

代码如下

class Solution {
    public int numDupDigitsAtMostN(int N) {
        String num = Integer.toString(N);
        char[] numArray = num.toCharArray();
        int[] array = new int[numArray.length];
        for (int i = 0; i < array.length; i++)  array[i] = (int) numArray[i] - '0';
        
        int distinct = getDistinct(array.length - 1); // 100, 1000, 10000这种
        Set<Integer> seen = new HashSet<>();
        for (int b = 0; b < array.length; b++) {
            for (int j = (b == 0 ? 1 : 0); j < ((b == array.length - 1) ? 1 : 0) + array[b]; j++) {
                if (seen.contains(j)) continue;
                distinct += getDistinct(10 - (b + 1), array.length - (b + 1) );
            }
            if (seen.contains(array[b])) break;
            seen.add(array[b]);
        }
        return N - distinct;
    }
   
    private int getDistinct(int tc, int n) {
        int distinct = 1;
        for (int i = 0; i < n; i++) {
            distinct *= (tc - (i));
        }
        return distinct;
    }

    private int getDistinct(int n) {
        if (n == 0) return 0;
        int distinct = 9;
        for (int i = 0; i < n - 1; i++)  distinct *= (10 - (i + 1));
        return distinct + getDistinct(n - 1) ;
    }
}