DeepSeek LeetCode 2376.统计特殊整数 public int countSpecialNumbers(int n)

这是 LeetCode 2376 题统计特殊整数。题目理解特殊整数十进制表示中每一位数字都不同的整数。例如123、20、5 都是特殊的但 11、121 不是。要求统计 [1, n] 范围内特殊整数的数量。解题思路数位 DP (Digit DP) 是标准解法1. 状态定义· pos当前处理到第几位· mask已使用的数字集合10 位二进制· isLimit是否受上界限制· isNum是否已经开始填数字处理前导零2. 核心逻辑· 从高位到低位 DFS· 每位只能选未使用过的数字· 注意处理前导零前导零不算使用数字 0代码实现javapublic int countSpecialNumbers(int n) {char[] digits Integer.toString(n).toCharArray();int m digits.length;// memo[pos][mask][isLimit][isNum]// 但 isLimit 和 isNum 最多 2 种状态可以简化Integer[][][] memo new Integer[m][1 10][2];return dfs(0, 0, true, false, digits, memo);}private int dfs(int pos, int mask, boolean isLimit, boolean isNum,char[] digits, Integer[][][] memo) {if (pos digits.length) {return isNum ? 1 : 0; // 形成了一个有效数字}int limitFlag isLimit ? 1 : 0;if (!isLimit isNum memo[pos][mask][limitFlag] ! null) {return memo[pos][mask][limitFlag];}int res 0;// 如果还没开始填数可以选择跳过当前位继续前导零if (!isNum) {res dfs(pos 1, mask, false, false, digits, memo);}// 确定当前位的上限int upper isLimit ? (digits[pos] - 0) : 9;// 确定起始数字int start isNum ? 0 : 1;for (int d start; d upper; d) {if (((mask d) 1) 0) { // d 未使用过res dfs(pos 1, mask | (1 d),isLimit (d upper), true, digits, memo);}}if (!isLimit isNum) {memo[pos][mask][limitFlag] res;}return res;}更优化的写法简化状态由于 isLimit 为 true 的情况很少可以只 memo 非限制状态javapublic int countSpecialNumbers(int n) {char[] digits Integer.toString(n).toCharArray();int m digits.length;Integer[][] memo new Integer[m][1 10];return dfs(0, 0, true, false, digits, memo);}private int dfs(int pos, int mask, boolean isLimit, boolean isNum,char[] digits, Integer[][] memo) {if (pos digits.length) {return isNum ? 1 : 0;}if (!isLimit isNum memo[pos][mask] ! null) {return memo[pos][mask];}int res 0;if (!isNum) {res dfs(pos 1, mask, false, false, digits, memo);}int upper isLimit ? (digits[pos] - 0) : 9;int start isNum ? 0 : 1;for (int d start; d upper; d) {if (((mask d) 1) 0) {res dfs(pos 1, mask | (1 d),isLimit (d upper), true, digits, memo);}}if (!isLimit isNum) {memo[pos][mask] res;}return res;}测试示例javapublic static void main(String[] args) {Solution s new Solution();System.out.println(s.countSpecialNumbers(20)); // 19System.out.println(s.countSpecialNumbers(5)); // 5System.out.println(s.countSpecialNumbers(100)); // }复杂度分析· 时间复杂度O(10 × 2^10 × 10) ≈ O(10240)非常快· 空间复杂度O(10 × 2^10) ≈ O(10240)关键点1. mask 用 10 位二进制记录哪些数字已使用2. isNum 区分前导零避免将 0 算作已使用3. isLimit 控制是否受 n 的每一位限制4. 记忆化只存储 !isLimit isNum 的状态