思路

位运算和集合论

通过将位运算和集合论结合，可以用来表示数位状态，用来作为数位dp的一部分使用。

具体方法是，对于从右到左第i位数，如果为1就代表i这个数在集合中。对于要枚举的范围不大（例如数位D，范围为0-9）的数来说，可以很方便地用一个整数来存储数位的访问状态。

取出第i位数和加入第i位数都是$O(D)$的时间复杂度。设集合为x，则取出放入操作可以用位运算求解：

取出：x >> i & 1
放入：1 << i | x

数位dp

通过记忆化搜索来找出所有可能的状态，这样可以把需要遍历的情况压缩到状态数乘以单个状态计算时间的大小，状态数在本体中为位数（很小）乘以$O(2^D)$，后者是集合可能有的所有情况。同时单个状态的计算时间通常是很小的。这样就大大减小了计算的量，可以高效地找出所有符合条件的情况。

对于数位问题的技巧

1.对于不能超过最大数`n`的解决方式

设置一个isLimit标志，表示当前位置是否受到约束，即如果超过s[i]则非法。若isLimit为true，则当前可以遍历的数就存在一个上限s[i]，否则为9。在记忆化搜索的过程中维护和更新这个标志。

2.对于前置不能存在0，又可能为空的解决方式

设置一个isNum标志，表示前一位是否有填数字。如果前一位空，则这一位可以空（直接遍历下一位），也可以填1-9；如果前一位不空，则这一位只能填0-9。

复杂度

时间复杂度: $O(mD2^D)$。其中m为s的长度，D为10。
空间复杂度: $O(m2^D)$。

Code

class Solution {

    public int countSpecialNumbers(int n) {
        char[] s = Integer.toString(n).toCharArray();
        int[][] memo = new int[s.length][1 << 10];
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }
        return dfs(0, 0, true, false, s, memo);
    }


    private int dfs(int i, int mask, boolean isLimit, boolean isNum, char[] s, int[][] memo) {

        if (i == s.length) {
            return isNum ? 1 : 0; // isNum 为 true 表示得到了一个合法数字
        }

        if (!isLimit && isNum && memo[i][mask] != -1) {
            return memo[i][mask]; // 之前计算过
        }
        int res = 0;
        if (!isNum) { // 可以跳过当前数位
            res = dfs(i + 1, mask, false, false, s, memo);
        }
        // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
        int up = isLimit ? s[i] - '0' : 9;
        // 枚举要填入的数字 d
        // 如果前面没有填数字，则必须从 1 开始（因为不能有前导零）
        for (int d = isNum ? 0 : 1; d <= up; d++) {
            if ((mask >> d & 1) == 0) { // d 不在 mask 中，说明之前没有填过 d
                res += dfs(i + 1, mask | (1 << d), isLimit && d == up, true, s, memo);
            }
        }
        if (!isLimit && isNum) {
            memo[i][mask] = res; // 记忆化
        }
        return res;
    }
}

2024-09-20 17:09:36 #LeetCode

思路