力扣（leetcode）每日一题 2376 统计特殊整数 | 数位dp

力扣（leetcode）每日一题 2376 统计特殊整数 | 数位dp | 暴力递归+记忆化搜索

embedded/2024/10/21 11:53:23/

题干

2376. 统计特殊整数

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

示例 1：

**输入：**n = 20
**输出：**19
**解释：**1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。

示例 2：

**输入：**n = 5
**输出：**5
**解释：**1 到 5 所有整数都是特殊整数。

示例 3：

**输入：**n = 135
**输出：**110
**解释：**从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。

提示：

1 <= n <= 2 * 109

题解 1 时间上过不了

public static int countSpecialNumbers(int n) {  int count = 0;  for (int i = 1; i <= n; i++) {  HashSet<Integer> set = new HashSet<>();  int tmp = i;  int c = 0;  while (tmp > 0) {  int i1 = tmp % 10;  set.add(i1);  c++;  tmp /= 10;  }  if (c != set.size()) {  count++;  }  }  return n - count;  }

题解 2

动态规划，有想过，但是实现失败了
还有考虑过数学技巧的，用公式硬凑，这个是死路


public static int countSpecialNumbers(int n) {  int[][] dp = new int[String.valueOf(n).length()][1 << 10];    // 这里初始化dp赋值-1  n的长度和2的10次方 记录数字1，2，3，4，5，6，7，8，9 是否有被使用过  for (int[] ints : dp) {  Arrays.fill(ints, -1);  }  return f(0, true, 0, false, String.valueOf(n), dp) - 1;  
}  public static int f(int index,        // 递归的位置  boolean isLimit,  // 最后有最高位的限制  int mask,         // 记录已经使用过的数字  boolean isNum,    // 是否开始组成数字  String n,         // 数字n  int[][] dp) {     // 记忆化搜索  if (index == n.length()) {  return 1;  }  if (dp[index][mask] != -1 && isNum & !isLimit) {  return dp[index][mask];  }  int res = 0;  if (!isNum) {  res += f(index + 1, false, mask, false, n, dp);  }  // 看是否受限制  int top = isLimit ? n.charAt(index) - '0' : 9; // 如果有限制，就取最高位，如果没有限制就取9  for (int i = isNum ? 0 : 1; i <= top; i++) {  // 当位数可以使用  if ((mask & (1 << i)) == 0) {  // 递归  res += f(index + 1,  isLimit && i == top,  // 如果本身有限制，这次又是取最高位，那么还是需要限制最高位  mask | (1 << i),             // 1进行左移i位 然后求与   比如00011 | 1<< 3 就是   00111                    true,                 // 如果isNum为false，那么i开始位是1    如果isNum为true  n,  dp);  }  }  if (isNum & !isLimit) {  dp[index][mask] = res;            // 只有是数字，并且没有限制的时候才进行记忆化  }  return res;  
}