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

🟠   🔖  数学 动态规划 回溯  🔗 力扣 LeetCode

题目

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

Example 1:

Input: n = 2

Output: 91

Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99

Example 2:

Input: n = 0

Output: 1

Constraints:

• 0 <= n <= 8

题目大意

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10^n 。

示例 1：

输入： n = 2

输出： 91

解释： 答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。

示例 2：

输入： n = 0

输出： 1

提示：

• 0 <= n <= 8

解题思路

1. n == 0 的特殊情况：

   • 只有一个数字 0，答案为 1。

2. 枚举长度为 1 到 n 的所有数字：

   • 长度为 1 的数字：10 个（0 到 9）。
   • 长度为 2 的数字：第一位有 9 种选择（不能为 0），第二位有 9 种选择（不能与第一位重复），共 9 * 9。
   • 长度为 3 的数字：第一位有 9 种选择，第二位有 9 种，第三位有 8 种（共 9 * 9 * 8）。
   • 依次类推。

3. 公式化计算：

   • 对于长度为 k 的数字，总的不同数字个数为： 9 * 9 * 8 * ... * (10 - k + 1)
   • 累加所有长度为 1 到 n 的结果即可。
   • 使用循环递推的方式计算每个长度的值，避免直接递归导致的额外开销。

时间复杂度

• 时间复杂度：O(n)，因为我们最多只计算 n 个长度的结果。
• 空间复杂度：O(1)，仅使用常数额外空间。

代码

/**
 * @param {number} n
 * @return {number}
 */
var countNumbersWithUniqueDigits = function (n) {
	if (n === 0) return 1; // 特殊情况

	let res = 10; // 包含长度为 1 的数字（0 到 9）
	let unique = 9; // 从第二位开始的独特数字组合数
	let availableNumber = 9; // 可供选择的数字数量

	while (n-- > 1 && availableNumber > 0) {
		unique *= availableNumber; // 更新当前长度的独特组合数
		res += unique; // 累加结果
		availableNumber--; // 剩余可选数字减少
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2376	统计特殊整数		数学 动态规划	🔴	🀄️ 🔗
3032	统计各位数字都不同的数字个数 II 🔒		哈希表 数学 动态规划	🟢	🀄️ 🔗