Leetcode - Count Numbers with Unique Digits

My code:

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n < 0) {
            return 0;
        }
        
        boolean[] isVisited = new boolean[10];
        long max = (long) Math.pow(10, n);
        int ret = 1;
        for (int i = 1; i < 10; i++) {
            isVisited[i] = true;
            ret += helper(i, max, isVisited);
            isVisited[i] = false;
        }
        return ret;
    }
    
    private int helper(int curr, long max, boolean[] isVisited) {
        int counter = 0;
        if (curr >= max) {
            return 0;
        }
        counter++;
        for (int i = 0; i < 10; i++) {
            if (!isVisited[i]) {
                int next = 10 * curr + i;
                isVisited[i] = true;
                counter += helper(next, max, isVisited);
                isVisited[i] = false;
            }
        }
        
        return counter;
    }
}

reference:
https://discuss.leetcode.com/topic/48001/backtracking-solution/2
想法就是构建独立的数字，如何保证unique呢？
用一个boolean[]
想法很简单，但是没做出来。
我一直想着用 排列组合。

然后这个算法速度很慢。
当 n <= 10 时，
复杂度是 O(n !)
当n > 10 时，因为不可能不出现重复的数字，所以复杂度就定下来了为
O(10 !)
其实还好。最大不过是 O(10 !)

但是他慢就慢在，我们只需要求出最大值，而不用算出所有的这些数字。而这个算法就把所有的数字全部找出来了，浪费了大量的时间。

还是得用排列组合的思想来解决。
于是DP算法出来了。
其实也不算正宗的DP

My code:

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n < 0) {
            return 0;
        }
        else if (n == 0){
            return 1;
        }
        else if (n == 1) {
            return 10;
        }
        
        int k = 0;
        if (n <= 10) {
            k = 9 - n + 2;            
        }
        else {
            k = 1;
        }
        
        int ret = 10;
        int base = 9;
        for (int i = 9; i >= k; i--) {
            base = base * i;
            ret += base;
        }
        
        return ret;
    }
}

reference:

• A direct way is to use the backtracking approach.
• Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
• This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
• Let f(k) = count of numbers with unique digits with length equals k.
• f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2) [The first factor is 9 because a number cannot start with 0].

其实就是这道题目的hint, 加粗的两点。

如果 1 <= k <= 10;
那么
f(k) = 9 * 9 * 8 * ... * (9 - k + 2)

然后算出来就行了。

Anyway, Good luck, Richardo! -- 08/27/2016