leetCode-357:Count Numbers with Unique Digits

问题描述

给定一个整数 n, 0 <= n <= 8，要求找出 0 <= x <= 10 ^ n 范围内各个位上数字不同的数的总数。题目链接：点我

样例输入输出

输入：2

输出：91

输入：0

输出：1

问题解法

这算是一道数学题，当 n 为 1，时，数字位数只有一位，总共有 0 ~ 9 10 个数字，当 n > 1 时，数位有多个，按从左到右算，第一位有 1 ~ 9 9个数字可以选择，第二位有 0 ~ 9 且除去第一位已经选择的数字，共有 9 个数字可以选，第三位有 0 ~ 9 且除去前两位已经选择的数字，共有 8 个数字可以选，第四位有 0 ~ 9 且除去前三位已经选择的数字，共有 7 个数字可以选，以此类推，可以算出当前位数的数字总数，然后把前面位数的数字总数相加，就能得到最终答案。代码如下

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }

        int current = 9;
        int result = 10;
        for (int i = 0; i < n - 1; i++) {
            current = current * (9 - i);
            result += current;
        }

        return result;
    }
}