LeetCode刷题实战357：计算各个位数不同的数字个数 / 开普饭

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 计算各个位数不同的数字个数，我们先来看题面：

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

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

示例

输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

解题

根据排列组合性质，如果是3位数那么，一共10个数字，第一个为1-9一共9个选择，第二个为0-9中去掉第一个数字，一共9个选择，第三个为去掉前两个数字，一共8个选择，那么答案为：998，同理，2位数为：9×9，1位数为10，因此，对于本题：

当n>1时：f(n) = f(n-1)*(10-n+1)，f(1)=9

当n==1时：返回10，当n为0时，返回0（只有0）

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        if(n==1) return 10;
        int result=10;
        int f=9;
       for (int i = 2; i <= n; ++i) {
        //从f(2)开始计算，然后累加即可
        f*=(10-i+1);
        result += f;
    }
        return result;
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode1-340题汇总，希望对你有点帮助！

LeetCode刷题实战341：扁平化嵌套列表迭代器

LeetCode刷题实战342：4的幂

LeetCode刷题实战343：整数拆分

LeetCode刷题实战344：反转字符串

LeetCode刷题实战345：反转字符串中的元音字母

LeetCode刷题实战346：数据流中的移动平均值

LeetCode刷题实战347：前 K 个高频元素

LeetCode刷题实战348：设计井字棋

LeetCode刷题实战349：两个数组的交集