A

题目

2427. 公因子的数目 - 力扣（LeetCode） (opens new window)

思路

1. 枚举

枚举所有公因子即可。

代码

class Solution {
public:
    int commonFactors(int a, int b) {
        int res = 0;
        for (int i = 1; i <= std::min(a, b); i ++) {
            if (a % i == 0 && b % i == 0) res ++;
        }
        return res;
    }
};

// Make sure to add code blocks to your code group

B

题目

2428. 沙漏的最大总和 - 力扣（LeetCode） (opens new window)

思路

1. 枚举

暴力枚举左上角端点即可。

代码

class Solution {
public:
  int maxSum(vector<vector<int>>& s) {
      int res = 0;
      int n = s.size(), m = s[0].size();
      
      for (int i = 0; i + 2 < n; i ++) {
          for (int j = 0; j + 2 < m; j ++) {
              int t = s[i][j] + s[i][j + 1] + s[i][j + 2] + s[i + 1][j + 1] + s[i + 2][j] + s[i + 2][j + 1] + s[i + 2][j + 2];
              res = std::max(res, t);
          }
      }
      return res;
  }
};

// Make sure to add code blocks to your code group

C

题目

2429. 最小 XOR - 力扣（LeetCode） (opens new window)

思路

1.贪心 + 分类讨论 + 位运算

首先我们令 z1 和 z2 分别表示 num1 和 num2 在二进制下的 1 的个数。

接下来分三种情况讨论：

1. z1 = z2 此时我们直接令 x = num1，即 return num1 即可。
2. z1 < z2 这种情况下，对于我们要求的 x，根据贪心的思想我们要先让 x 在 num1 原本二进制位下为 1 的那些位赋值为 1，因为这样在 x 与 num1 异或后原本 num1 二进制下为 1 的那些位就为 0 了，接着多出来的 1，也就是 z2 - z1，我们对 x 从低位到高位将其二进制位仍为 0 的位依次赋值即可。
3. z1 > z2 在这种情况下，我们是要去尽可能削减 num1 的值，因此我们将 z2 个 1，依次从高位到低位看 num1 的每一位是否为 1，依次给 x 赋值来抵消即可。

代码

class Solution {
public:
  int minimizeXor(int num1, int num2) {
      int z1 = __builtin_popcount(num1), z2 = __builtin_popcount(num2);
      if (z1 == z2) return num1;
      
      if (z1 < z2) {
          int dif = z2 - z1;
          int res = 0;
          for (int i = 0; i < 32; i ++) {
              int z = num1 >> i & 1;
              if (!z) {
                  num1 ^= 1 << i;
                  dif --;
              }
              if (!dif) return num1;
          }
      } else {
          int res = 0;
          for (int i = 31; ~i; i --) {
              int z = num1 >> i & 1;
              if (z) {
                  res ^= 1 << i;
                  z2 --;
              }
              if (!z2) return res;
          }
      }
      return 1;
  }
};

// Make sure to add code blocks to your code group

D

题目

2430. 对字母串可执行的最大删除数 - 力扣（LeetCode） (opens new window)

思路

1. DP

我们先令 表示对 可执行的最大删除数，我们枚举这一次的删除长度 ，如果满足 ，即满足删除条件，就可以很容易得到状态转移方程 。最后输出 即可，在最后输出的时候需要 + 1 是因为我们字符串删到最后一步，一定是整个字符串全部删除，即找不到满足可以删除条件的长度 。

参考：线性 DP（Python/Java/C++/Go） - 对字母串可执行的最大删除数 - 力扣（LeetCode） (opens new window)

代码

class Solution {
public:
  int deleteString(string s) {
      int n = s.size();
      std::vector dp(n + 1, std::vector<int> (n + 1));

      for (int i = n - 1; ~i; i --) {
          for (int j = n - 1; ~j; j --) {
              if (s[i] == s[j]) {
                  dp[i][j] = dp[i + 1][j + 1] + 1;
              }
          }
      }

      std::vector<int> f(n + 1);
      for (int i = n - 1; ~i; i --) {
          for (int j = 1; i + 2 * j - 1 < n; j ++) {
              if (dp[i][i + j] >= j) {
                  f[i] = std::max(f[i], f[i + j] + 1);
              }
          }
      }

      return f[0] + 1;
  }
};

// Make sure to add code blocks to your code group

2.非正解 DFS (本题数据交水，正常情况过不了本题)

暴搜所有的情况，加上记忆化 和 对特殊样例的特判即可，由于非正解就不细说了。。。

代码

class Solution {
public:
  int n;
  std::vector<int> f;
  int deleteString(string s) {
      n = s.size();
      std::vector<int> to[n];
      f.resize(n);
      std::set<char> S;
      for (auto x : s) 
          S.insert(x);
      if (S.size() == 1) return n;
      int INF = 1e9;
      for (int i = 0; i < n; i ++) {
          for (int z = 1; i + 2 * z - 1 < n && z <= n; z ++) {
              int cnt = 0;
              for (int k = 0; k < z; k ++) { 
                  if (s[i + k] == s[i + k + z]) {
                      cnt ++;
                  } else {
                      cnt = INF;
                      break;
                  }
              }
              if (cnt != INF) to[i].emplace_back(cnt);
          }
      }
      return dfs(0, to);
  }
  int dfs(int u, std::vector<int> to[]) {
      if (to[u].size() == 0) return 1;
      if (f[u]) return f[u];
      int rax = -1;
      for (auto len : to[u]) {
          rax = std::max(dfs(u + len, to), rax);
          if (rax == n - u - 1) break;
      }
      return f[u] = rax + 1;
  };
};

// Make sure to add code blocks to your code group