Medium

题目描述

给你一个整数 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

解题提示：

  • 直接方法是使用回溯法
  • 回溯应该包含三个状态：当前数字、构成该数字的步数、以及表示当前数字中已访问数字的位掩码
  • 也可以使用动态规划和组合数学知识解决
  • 设 f(k) = 长度为 k 且各位数字都不同的数字个数
  • f(1) = 10，f(k) = 9 × 9 × 8 × … × (9 - k + 2)（第一个因子是9因为数字不能以0开头）

解题思路

这道题可以用数学组合的方法来解决，这是最优解法。

核心思路：

  • 对于 n 位数字，我们需要统计所有位数小于等于 n 且各位数字都不同的数字个数
  • 分别计算 1位数、2位数、…、n位数的各位数字都不同的数字个数

计算方法：

  1. 1位数：0-9，共10个数字，都满足条件
  2. k位数 (k≥2)：
    • 第一位不能是0，有9种选择 (1-9)
    • 第二位不能与第一位相同，有9种选择 (包括0，但排除第一位)
    • 第三位不能与前两位相同，有8种选择
    • …
    • 第k位有 (11-k) 种选择
    • 所以k位数的个数为：9 × 9 × 8 × … × (11-k)

特殊情况：

  • n=0 时，只有数字0符合条件，返回1
  • 当 n>10 时，由于数字只有0-9共10个，无法构成超过10位的各位数字都不同的数字

其他解法：

  • 回溯法：枚举所有可能的数字组合，用位掩码记录已使用的数字
  • 动态规划：状态为当前位数和已使用数字的集合

数学解法时间复杂度最优，推荐使用。

代码实现

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        
        int result = 10; // 1位数：0-9
        int uniqueDigits = 9;
        int availableNumber = 9;
        
        while (n-- > 1 && availableNumber > 0) {
            uniqueDigits = uniqueDigits * availableNumber;
            result += uniqueDigits;
            availableNumber--;
        }
        
        return result;
    }
};

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        
        result = 10  # 1位数：0-9
        unique_digits = 9
        available_number = 9
        
        while n > 1 and available_number > 0:
            unique_digits *= available_number
            result += unique_digits
            available_number -= 1
            n -= 1
        
        return result

public class Solution {
    public int CountNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        
        int result = 10; // 1位数：0-9
        int uniqueDigits = 9;
        int availableNumber = 9;
        
        while (n-- > 1 && availableNumber > 0) {
            uniqueDigits *= availableNumber;
            result += uniqueDigits;
            availableNumber--;
        }
        
        return result;
    }
}

var countNumbersWithUniqueDigits = function(n) {
    if (n === 0) return 1;
    
    let result = 10; // for n = 1: 0-9
    let uniqueDigits = 9; // first digit choices (1-9)
    let availableDigits = 9; // remaining digit choices
    
    for (let i = 2; i <= n; i++) {
        uniqueDigits *= availableDigits;
        result += uniqueDigits;
        availableDigits--;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(1)

相关题目