2376. 统计特殊整数(2120)

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= n <= 2 * 10^9

思路：记忆化搜索dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    char s[];
    int memo[][];  // 记忆化
    public int countSpecialNumbers(int n) {
        s = String.valueOf(n).toCharArray();
        memo = new int[s.length][1 << 10];
        for (int i = 0; i < s.length; i++) Arrays.fill(memo[i], -1);
        return dfs(0, 0, true, false);
    }
    // i: 当前数位
    // mask: 已经选过的数字
    // isLimit: 是否有上界（例如数字123，如果前两位选取1和2，那么此时有上界，第三位只能选1 2 3）
    // isNum: 是否已经选过数字（例如数字123，如果第一位选择跳过当前数位，则isNum仍为false，否则为true）
    public int dfs(int i, int mask, boolean isLimit, boolean isNum) {
        if (i == s.length) return isNum ? 1 : 0;
        if (!isLimit && memo[i][mask] != -1) return memo[i][mask];
        int res = 0;
        if (!isNum) res = dfs(i+1, mask, false, false);  // 选择跳过当前数位
        int up = isLimit ? s[i]-'0' : 9;
        for (int d = isNum ? 0 : 1; d <= up; d++) {  // 选取当前数位
            if ((mask >> d & 1) == 0) res += dfs(i+1, mask|(1<<d), isLimit && d==up, true);
        }
        if (!isLimit && isNum) memo[i][mask] = res;  // isLimit=false isNum=true 的情况不需要记忆化
        return res;
    }
}