@@ -0,0 +1,2116 @@
+package dynamic_programming.one_d_dp;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.HashSet;%0Aimport java.util.List;%0Aimport java.util.Set;%0A%0Apublic class Q1015NumbersWithRepeatedDigits %7B%0A%0A    //Difficulty: Hard%0A    //TAG: DP%0A    //TODO: https://leetcode.com/problems/numbers-with-repeated-digits/discuss/256725/JavaPython-Count-the-Number-Without-Repeated-Digit%0A%0A    /**%0A     * 1015. Numbers With Repeated Digits%0A     * Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.%0A     *%0A     *%0A     *%0A     * Example 1:%0A     *%0A     * Input: 20%0A     * Output: 1%0A     * Explanation: The only positive number (%3C= 20) with at least 1 repeated digit is 11.%0A     * Example 2:%0A     *%0A     * Input: 100%0A     * Output: 10%0A     * Explanation: The positive numbers (%3C= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.%0A     * Example 3:%0A     *%0A     * Input: 1000%0A     * Output: 262%0A     *%0A     *%0A     * Note:%0A     *%0A     * 1 %3C= N %3C= 10%5E9%0A     */%0A%0A    /*%0A    Solution:%0A    dp find all non-repeat number numbers smaller than N, then N - count%0A    https://leetcode.com/problems/numbers-with-repeated-digits/discuss/256725/JavaPython-Count-the-Number-Without-Repeated-Digit%0A     */%0A%0A    public int numDupDigitsAtMostN(int N) %7B%0A        // Transform N + 1 to arrayList%0A        List%3CInteger%3E L = new ArrayList%3C%3E();%0A        for (int x = N + 1; x %3E 0; x /= 10)%0A            L.add(0, x %25 10);%0A%0A        // Count the number with digits %3C N%0A        int res = 0, n = L.size();%0A        for (int i = 1; i %3C n; ++i)%0A            res += 9 * A(9, i - 1);%0A%0A        // Count the number with same prefix%0A        Set%3CInteger%3E seen = new HashSet%3C%3E();%0A        for (int i = 0; i %3C n; ++i) %7B%0A            for (int j = i %3E 0 ? 0 : 1; j %3C L.get(i); ++j)%0A                if (!seen.contains(j))%0A                    res += A(9 - i, n - i - 1);%0A            if (seen.contains(L.get(i))) break;%0A            seen.add(L.get(i));%0A        %7D%0A        return N - res;%0A    %7D%0A%0A%0A    public int A(int m, int n) %7B%0A        return n == 0 ? 1 : A(m, n - 1) * (m - n + 1);%0A    %7D%0A%0A%7D%0A

1015. Numbers With Repeated Digits