记忆化搜索与动态规划专题力扣题目总结

i 表示当前填到了第几位
mask 表示已经填过的数字, 这里可以用状态压缩, 使用一个大小为1<<10的整数表示状态(哪些数字用过了) 主要用来增加限制条件
is_limit 表示当前位s[i]是否受到前一位的约束, 例如, 前一位是 0, 则当前位无限制, 前一位达到了所能填的最大值, 则当前位能填0~s[i], 主要用来约束填的数字
is_num 表示当前位是否填了数字, 如果填过, 就可以从0~9中任选, 没填过的话需要从1~9开始. (可以跳过不填) 主要用来约束前导零

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

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

class Solution { // n 位且各位都不相同的整数数目
public:
    int countSpecialNumbers(int n) {
        auto s = to_string(n);
        int m = s.size(), dp[m][1 << 10];
        memset(dp, -1, sizeof(dp)); // -1 表示没有计算过
        function<int(int, int, bool, bool)> f =
            [&](int i, int mask, bool is_limit, bool is_num) -> int {
            if (i == m) return is_num; // is_num 为 true 表示得到了一个合法数字, 填过之后才记录答案
            if (!is_limit && is_num && dp[i][mask] != -1) //  有限制的只有一次并且并未放入缓存, 只有没限制时才读取缓存
                return dp[i][mask];
            int res = 0;
            if (!is_num) // 可以跳过当前数位
                res = f(i + 1, mask, false, false);// 跳过了, 则没有限制了
            int up = is_limit ? s[i] - '0' : 9;
            // 如果前面填的数字都和 n 的一样，那么这一位至多填数字
            // s[i]（否则超过 n)
            for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d, 这里要求从 1 开始
                if ((mask >> d & 1) == 0)          // d 不在 mask 中
                    res += f(i + 1, mask | (1 << d), is_limit && d == up, true);
            if (!is_limit && is_num) // 有限制 这种情况之后不会再次出现, 所以不需要记忆
                dp[i][mask] = res;
            return res;
        };
        return f(0, 0, true, false); // 后面要填的数字要受到限制(因为还没跳过), 并且还没填数字
    }
};

一些有趣的位运算技巧

if (~x) // 当 x 不是-1 时候为真, 下同
for (int i{n - 1}; ~i ; --i) // i 可取 n - 1 到 0
mask >> d & 1 // 取出 mask 的第 d 位
mask & (1 << d) // 同上
mask |= 1 << d // 设置 mask 第 d 位为 1
mask &= ~(1 << d) // 设置 mask 第 d 位为 0

题目: 十进制数位

直接掩码

2376. 统计特殊整数;(需要考虑四个状态的转移, 是一种普遍的模板)

class Solution {
public:
    int countSpecialNumbers(int n) {
        auto s = to_string(n);
        int m = s.size(), dp[m][1 << 10];
        memset(dp, -1, sizeof(dp));
        function<int(int, int, bool, bool)> f =
            [&](int i, int mask, bool is_limit, bool is_num) -> int {
            if (i == m) return is_num;
            if (!is_limit && is_num && ~dp[i][mask]) return dp[i][mask];
            int ans{};
            if (!is_num) ans = f(i + 1, mask, false, false);
            int up = (is_limit ? s[i] - '0' : 9);
            for (int d{1 - is_num}; d <= up; ++d)
                if ((mask & (1 << d)) == 0)
                    ans += f(i + 1, mask | (1 << d), is_limit && d == up, true);
            if (!is_limit && is_num) dp[i][mask] = ans;
            return ans;
        };
        return f(0, 0, true, false);
    }
};

1012. 至少有 1 位重复的数字 - 力扣（LeetCode）;(和上一个题是互为相反的结果)

class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        auto s = to_string(n);
        int m = s.size(), dp[m][1 << 10];
        memset(dp, -1, sizeof(dp));
        function<int(int, int, bool, bool)> f =
            [&](int i, int mask, bool is_limit, bool is_num) -> int {
            if (i == m) return is_num;
            if (!is_limit && is_num && ~dp[i][mask]) return dp[i][mask];
            int ans{};
            if (!is_num) ans = f(i + 1, mask, false, false);
            int up = (is_limit ? s[i] - '0' : 9);
            for (int d{1 - is_num}; d <= up; ++d)
                if ((mask & (1 << d)) == 0)
                    ans += f(i + 1, mask | (1 << d), is_limit && d == up, true);
            if (!is_limit && is_num) dp[i][mask] = ans;
            return ans;
        };
        return n - f(0, 0, true, false); // 只有这里不同
    }
};

考虑数量

233. 数字 1 的个数 - 力扣（LeetCode）;

class Solution {
public:
    int countDigitOne(int n) {
        auto s = to_string(n);
        int m = s.size(), dp[m][m];
        memset(dp, -1, sizeof(dp));
        function<int(int, int, bool)> f = [&](int i, int cnt,
                                              bool is_limit) -> int {
            if (i == m) return cnt;
            if (!is_limit && ~dp[i][cnt]) return dp[i][cnt];
            int ans{};
            int up = is_limit ? s[i] - '0' : 9;
            for (int d{}; d <= up; ++d)
                ans += f(i + 1, cnt + (d == 1), is_limit && d == up);
            if (!is_limit) dp[i][cnt] = ans;
            return ans;
        };
        return f(0, 0, true);
    }
};

面试题 17.06. 2出现的次数 - 力扣（LeetCode）;

class Solution {
public:
    int numberOf2sInRange(int n) {
        auto s = to_string(n);
        int m = s.size(), dp[m][m];
        memset(dp, -1, sizeof(dp));
        function<int(int, int, bool)> f = [&](int i, int cnt, bool is_limit) {
            if (i == m) return cnt;
            if (!is_limit && ~dp[i][cnt]) return dp[i][cnt];
            int ans{}, up = is_limit ? s[i] - '0' : 9;
            for (int d{}; d <= up; ++d)
                ans += f(i + 1, cnt + (d == 2), is_limit && up == d);
            if (!is_limit) dp[i][cnt] = ans;
            return ans;
        };
        return f(0, 0, true);
    }
};

902. 最大为 N 的数字组合 - 力扣（LeetCode）;

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        auto s = to_string(n);
        int m = s.size(), dp[m];
        memset(dp, -1, sizeof(dp));
        function<int(int, bool, bool)> f = [&](int i, bool is_limit,
                                               bool is_num) -> int {
            if (i == m) return is_num;
            if (!is_limit && is_num && ~dp[i]) return dp[i];
            int ans{};
            if (!is_num) ans = f(i + 1, false, false);
            int up{is_limit ? s[i] - '0' : 9};
            for (auto d : digits) {
                int tmp{d[0] - '0'};
                if (tmp > up) break;
                ans += f(i + 1, is_limit && up == tmp, true);
            }
            if (!is_limit && is_num) dp[i] = ans;
            return ans;
        };
        return f(0, true, false);
    }
};

2719. 统计整数数目;

题目: 二进制数位

600. 不含连续1的非负整数 - 力扣（LeetCode）;

class Solution {
public:
    int findIntegers(int n) {
        int m = __lg(n), dp[m + 1][2];
        memset(dp, -1, sizeof(dp));
        function<int(int, bool, bool)> f = [&](int i, bool is_limit,
                                               bool is_pre1) {
            if (i < 0) return 1;
            if (!is_limit && ~dp[i][is_pre1]) return dp[i][is_pre1];
            int up = is_limit ? n & (1 << i) : 1;
            int ans = f(i - 1, is_limit && up == 0, false);      // 0
            if (!is_pre1 && up) ans += f(i - 1, is_limit, true); // 1
            if (!is_limit) dp[i][is_pre1] = ans;
            return ans;
        };
        return f(m, true, false); // 反着遍历
    }
};

__lg(n)代表获取数字 n 的最高有效位的位置(从低位到高位), 只存在于 GNU 编译器, 但是力扣的 clang11 竟然也支持, 猜测可能是包含了 GNU C++的stl_algobase.h. (下面是一个可能的实现)

  int my__lg(int x) {
     int ans{};
     for (; x; x >>= 1) ++ans;
     return ans - 1; // 默认从零开始索引
  }

更多有用的函数可以参考: gcc document; (虽然可以极大地方便刷算法题, 但是并不要在代码中用双下划线开头的函数, 不安全)

此外, 还有一些很有用的位运算相关函数: (GCC)

  Built-in Function: int __builtin_ffs (unsigned int x) // 返回 1 加上 x 的最低有效 1 位的索引
  Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
  Built-in Function: int __builtin_clz (unsigned int x) // 返回前导零数目(默认是 32 位情况)
  Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
  Built-in Function: int __builtin_ctz (unsigned int x) // 返回尾置零的数目
  Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
  Built-in Function: int __builtin_popcount (unsigned int x) // 返回 1 的数目, 很常用
  Returns the number of 1-bits in x.

甚至可以用内置方法实现__lg(): (前提是保证输入数据低于 32 位)

  auto f = [](int n) { return 32 - __builtin_clz(n) - 1; }; // 这里直接减去得到的是去除前导零的位数, 要获取最高有效位的位置还需要减去 1, 因为默认从 0 开始索引
  auto g = [](int n) { return __lg(n); };
  printf("bit: %d\n", f(x)); // 3
  printf("bit: %d\n", g(x)); // 3

题目: 字符串

1397. 找到所有好字符串 - 力扣（LeetCode）;(KMP-algo)

上篇深度探索c++对象模型笔记(第二章)构造函数语义学

下篇字典树力扣题目总结