Count Numbers with Unique Digits

https://leetcode.com/problems/count-numbers-with-unique-digits/description/

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:

Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Credits:

Special thanks to @memoryless for adding this problem and creating all test cases.

Thoughts

排列组合，例如n=4则四位数每个数字不相同的个数是9 * 9 * 8 * 7. 由于首位不能是0所以是9而不是10. 由于返回的不止n位数的，还有返回所有0~n-1位数的所有可能。而三位数为9*9*8，因为f(n) = f(n-1) * j.

Code

  class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        int res = 0;
        if (n == 0) {
            res += 1;
            return res;
        } 
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 9;
        for (int i = 2, j = 9; i <= n && j > 0; i++, j--) {
            f[i] = f[i - 1] * j; 
        }
        for (int i = 0; i <= n; i++) {
            res += f[i];
        }
        return res;
    }
}

Analysis

做题耗时30min.

Errors:

1. 开始误以为直接返回10 * 9 * 8 ...即可，但这样少了060这样的数。

时间复杂度为O(n).