leetcode
leetcode 2651 ~ 2700
统计各位数字都不同的数字个数

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

难度:

标签:

题目描述

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

 

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

代码结果

运行时间: 20 ms, 内存: 0.0 MB

// 思路：使用Java Stream来生成所有0到10^n的数字流，
// 过滤出各位不重复的数字并统计数量。

import java.util.stream.IntStream;

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int limit = (int) Math.pow(10, n);
        return (int) IntStream.range(0, limit)
                .filter(Solution::hasUniqueDigits)
                .count();
    }

    private static boolean hasUniqueDigits(int num) {
        boolean[] seen = new boolean[10];
        while (num > 0) {
            int digit = num % 10;
            if (seen[digit]) return false;
            seen[digit] = true;
            num /= 10;
        }
        return true;
    }
}

解释

方法:

这个题解使用了数学方法来解决问题。对于一个n位数，第一位有9种选择（不能为0），第二位有9种选择，第三位有8种选择，以此类推。所以不同的n位数的个数为9*9*8*...(9-n+2)，再加上小于n位数的不同数字的个数，即为最终结果。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算不同数字的个数时，第一位数字的选择范围是9而不是10？
▷
在计算一个n位数时，第一位数字不能为0（除非数字本身是0），因为如果第一位为0，则它不会被视为一个n位数，而是一个n-1位数。例如，'0123'实际上是一个三位数123。因此，第一位的选择范围是1到9，共9种可能。
🦆
在题解中提到'第二位有9种选择'，这种说法是否准确？是否应该是10-1=9种选择因为已经选择了一个数字？
▷
这种说法基本上是准确的，但表述可能略有混淆。实际上，第二位数字的选择范围应该是除了已经选过的第一位数字之外的所有数字。如果第一位选择了一个数字，那么第二位可以选择的数字实际上是剩下的9个数字（10个数字中去除已经选择的1个）。因此，第二位有10-1=9种选择。
🦆
对于n=0的情况，为什么输出是1？是否可以解释一下这种特殊情况的逻辑？
▷
在这种情况下，n=0意味着我们考虑的是0位数字的数量。在数学和数字的定义中，0位数字可以看作是不存在任何数字，即空数列。在这种情况下，我们通常认为存在一个这样的数字，即'数的空集'，对应于数字0。因此，对于n=0，我们认为只有一个数（即0），所以输出为1。

相关问题

4的幂水壶问题