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``。题目返回计数,不需要列出这些整数。 自建示例 -------- 只考察一位数: .. code-block:: text 输入:n = 1 输出:10 解释:范围是 0 到 9,每个数的十进制表示最多只有一位,不可能出现重复数字。 三位范围: .. code-block:: text 输入: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++ 实现 -------- .. code-block:: cpp 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))``。