0357. Count Numbers with Unique Digits

题目信息

题号:

0357

难度:

Medium

主题:

十进制数字、计数、组合、边界

原题:

LeetCode 0357

重点:

统计范围为 0 <= x < 10^n、数字表示中各位互不相同、前导零不属于表示、n=0 只包含数字 0

题目重述

给定整数 n,统计所有满足 0 <= x < 10^n,且十进制表示中没有任何重复数字的整数数量。整数的通常十进制表示不包含前导零,因此例如 7 只包含一位数字,而不是被视为 007。

n 位于 [0, 8]。数字 0 本身符合条件;当 n=0 时,范围为 [0,1),答案为 1。题目返回计数,不需要列出这些整数。

自建示例

只考察一位数:

输入:n = 1
输出:10
解释:范围是 0 到 9,每个数的十进制表示最多只有一位,不可能出现重复数字。

三位范围:

输入:n = 3
输出:739
解释:答案包含 0、一位数、两位数和三位数;每个整数都按不带前导零的正常表示检查数字是否重复。

按实际位数计数,首位与后续位分开

范围 0 <= x < 10^n 包含位数从 0 到 n 的所有非负整数。数字 0 单独贡献一种空范围意义上的计数;对于长度至少 1 的普通十进制表示,首位不能为 0,所以有 9 种选择,之后每增加一位,可用数字数依次为 9、8、7……。

例如长度为 3 的数字有 9 * 9 * 8 种:第一位从 1 到 9,第二位可以选剩余的 9 个数字,第三位再从剩余 8 个数字中选。把各个长度的计数累加即可;题目范围最多 8 位,不会遇到十进制数字耗尽的问题。

C++ 实现

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        n = std::min(n, 10);
        int result = 1;  // 数字 0
        int ways = 1;
        int available = 9;

        for (int length = 1; length <= n; ++length) {
            ways *= (length == 1 ? 9 : available);
            result += ways;
            if (length > 1) --available;
        }
        return result;
    }
};

代码分析

ways 表示当前位数的完整计数,首位使用 9 个非零数字,后续位从未使用数字中选择;结果初始的 1 覆盖数字 0 和 n == 0。循环长度最多 10,时间和额外空间均为 O(min(n, 10))。