LeetCode 357. 统计各位数字都不同的数字个数题目描述给你一个整数 n统计并返回各位数字都不同的数字 x 的个数其中 0 x 10^n。示例输入: n 2 输出: 91 解释: 答案应为除去 11、22、33、44、55、66、77、88、99 外 在 [0,100) 区间内的所有数字共 91 个。 输入: n 0 输出: 1 解释: 只有数字 0。思路分析这道题是排列组合问题。位数不超过 n 的数可以按位数分类统计· 0 位数只有数字 0 本身 → 1 个特殊处理· 1 位数1~9第一位有 9 种选法1-9→ 9 个· 2 位数第一位 9 种1-9第二位有 9 种0-9 去掉已选的→ 9 × 9 81· 3 位数第一位 9 种第二位 9 种第三位 8 种 → 9 × 9 × 8· k 位数第一位 9 种之后每一位可选 (10 - i) 种其中 i 为已填位数设 f(k) 为恰好 k 位数中各位数字不同的个数f(1) 9 f(k) 9 × 9 × 8 × 7 × ... × (11 - k) 共 k 个因子k 2答案 1 f(1) f(2) … f(n)注意当 k 10 时根据鸽巢原理10 个数字位选 k 个必然重复f(k) 0。代码实现classSolution{publicintcountNumbersWithUniqueDigits(intn){if(n0)return1;inttotal1;// 数字 0intunique9;// 当前位数的各位不同数字个数初始为 1 位数的情况for(inti1;in;i){if(i1){unique9;}else{uniqueunique*(11-i);// 第 i 位可选 10-(i-1) 11-i 种}totalunique;}returntotal;}}更简洁的写法classSolution{publicintcountNumbersWithUniqueDigits(intn){if(n0)return1;inttotal1;// 0 本身intunique9;// 1 位数1~9totalunique;// 累加 1 位数for(inti2;in;i){uniqueunique*(10-(i-1));// 第 i 位剩余可选数totalunique;}returntotal;}}手动推演以 n 3 为例位数 计算过程 个数0 位数 0 11 位数 9 92 位数 9 × 9 813 位数 9 × 9 × 8 648合计 739以 n 2 为例1 9 81 91 ✅ 与示例一致。复杂度分析· 时间复杂度 O(n)一次遍历。· 空间复杂度 O(1)仅用常数额外变量。关键细节n 0 单独处理此时 0 x 1只有 x 0答案为 1。n 10 时当位数超过 10必然出现重复数字unique 会在 i 11 时变为 0后续累加无影响循环自然不会出错也可直接 n Math.min(n, 10) 提前截断。为什么第 i 位是 11 - i· 第 1 位最高位非零9 种1-9· 第 2 位10 - 1 9 种0-9 排除已用 1 个· 第 3 位10 - 2 8 种· 第 i 位10 - (i - 1) 11 - i 种 ✅测试用例publicstaticvoidmain(String[]args){SolutionsnewSolution();System.out.println(s.countNumbersWithUniqueDigits(0));// 1System.out.println(s.countNumbersWithUniqueDigits(1));// 10System.out.println(s.countNumbersWithUniqueDigits(2));// 91System.out.println(s.countNumbersWithUniqueDigits(3));// 739System.out.println(s.countNumbersWithUniqueDigits(10));// 8877691}一句话总结按位数分类 排列组合递推每多一位可选的数字就少一个。这是本题最清晰的数学解法O(n) 时间、O(1) 空间。