LeetCode 357. 统计各位数字都不同的数字个数

357. 统计各位数字都不同的数字个数

题目来源：357. 统计各位数字都不同的数字个数

2022.04.11 每日一题

LeetCode 题解持续更新中GitHub仓库地址 CSDN博客地址

法一：打表法

YYDS

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        int dp[] = {1, 10, 91, 739, 5275, 32491, 168571, 712891, 2345851};
        return dp[n];
    }
};

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        int[] dp = new int[]{1, 10, 91, 739, 5275, 32491, 168571, 712891, 2345851};
        return dp[n];
    }
}

法二：正常推导

这个方法就是比较中规中矩的，一步一步推导的

高中的排列组合就可以啦

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        int ans = 10, cur = 9;
        for (int i = 0; i < n - 1; ++i) {
            cur *= 9 - i;
            ans += cur;
        }
        return ans;
    }
};

class Solution {
	public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        int ans = 10, cur = 9;
        for (int i = 0; i < n - 1; ++i) {
            cur *= 9 - i;
            ans += cur;
        }
        return ans;
    }
}