leetcode contest 312

前三题的题目也确实太水了。

6192. 公因子的数目

题目

给你两个正整数 a 和 b ，返回 a 和 b 的 公 因子的数目。

如果 x 可以同时整除 a 和 b ，则认为 x 是 a 和 b 的一个 公因子 。

示例 1：

输入：a = 12, b = 6
输出：4
解释：12 和 6 的公因子是 1、2、3、6 。

示例 2：

输入：a = 25, b = 30
输出：2
解释：25 和 30 的公因子是 1、5 。

提示：

• 1 <= a, b <= 1000

地址

https://leetcode.cn/problems/number-of-common-factors/

题意

模拟

思路

1. 因为数据量实在太小，直接暴力即可。
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 给定的数的大小。
• 空间复杂度：$O(1)$。

代码

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

6193. 沙漏的最大总和

题目

给你一个大小为 m x n 的整数矩阵 grid。
按以下形式将矩阵的一部分定义为一个 沙漏 ：
返回沙漏中元素的 最大 总和。
注意：沙漏无法旋转且必须整个包含在矩阵中。

示例 1：

输入：grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]
输出：30
解释：上图中的单元格表示元素总和最大的沙漏：6 + 2 + 1 + 2 + 9 + 2 + 8 = 30 。

示例 2：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：35
解释：上图中的单元格表示元素总和最大的沙漏：1 + 2 + 3 + 5 + 7 + 8 + 9 = 35 。

提示：

• m == grid.length
• n == grid[i].length
• 3 <= m, n <= 150
• 0 <= grid[i][j] <= 106

地址

https://leetcode.cn/problems/maximum-sum-of-an-hourglass/

题意

枚举中心

思路

1. 设矩阵的行列分别为 $m,n$，根据题意我们枚举所有可能的中心位置 $x$，可以知道以 $(x,y)$ 为中心的位置的沙漏元素和为 $grid[x][y] + \sum_{i = y - 1}^{y+1} \limits (grid[x-1][i] + grid[x+1][i])$，我们依次求出可能的沙漏值即可。
2. 复杂度分析：

• 时间复杂度：时间复杂度为 $O(m \times n)$，其中 $m,n$ 表示矩阵的行与列。
• 空间复杂度：空间复杂度为 $O(1)$。

代码

class Solution {
public:
    int maxSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                int tot = grid[i][j];
                for (int k = j - 1; k <= j + 1; k++) {
                    tot += grid[i-1][k];
                    tot += grid[i+1][k];
                }
                ans = max(ans, tot);
            }
        }
        return ans;
    }
};

6194. 最小 XOR

题目

给你两个正整数 num1 和 num2 ，找出满足下述条件的整数 x ：

• x 的置位数和 num2 相同，且
• x XOR num1 的值 最小
  注意 XOR 是按位异或运算。

返回整数 x 。题目保证，对于生成的测试用例， x 是 唯一确定 的。

整数的 置位数 是其二进制表示中 1 的数目。

示例 1：

输入：num1 = 3, num2 = 5
输出：3
解释：
num1 和 num2 的二进制表示分别是 0011 和 0101 。
整数 3 的置位数与 num2 相同，且 3 XOR 3 = 0 是最小的。

示例 2：

输入：num1 = 1, num2 = 12
输出：3
解释：
num1 和 num2 的二进制表示分别是 0001 和 1100 。
整数 3 的置位数与 num2 相同，且 3 XOR 1 = 2 是最小的。

提示：

• 1 <= num1, num2 <= 109

地址

https://leetcode.cn/problems/minimize-xor/

题意

贪心

思路

1. 典型的贪心熟路，设 $n$ 表示 $nums2$ 的位数，$m$ 表示 $nums1$ 的二进制中的 $1$ 最高位数，则有以下两种情况:

• $m \le n$: 此时我们只能选择在最低的 $n$ 位全部填充为 $1$ 即可，此时返回结果为 $2^n - 1$；
• $m > n$: 此时我们只能选择在低 $m$ 位选择 $n$ 位填充为 $1$ 即可：
  • 首先按照异或的规则，我们应当先在 $nums1$ 中从高到低的位数中为 $1$ 的位中填写 $1$，这样就可以优先将 $nums1$ 中高位的 $1$ 消为 $0$；
  • 如果将 $nums1$ 中的 $1$ 全部消掉，如果 $n$ 仍然还大于 $0$，此时我们应当贪心的在 $nums1$ 中从低往高的位数中为 $0$ 位中填写 $1$，这样保证形成的数最小；

2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(\log (nums1) + \log (nums2))$，$nums1,nums2$ 为给定的数。
• 空间复杂度：时间复杂度为 $O(\log (nums1))$，$nums1,nums2$ 为给定的数。

代码

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int n = __builtin_popcount(num2);
        vector<int> arr;
        while(num1 > 0) {
            arr.emplace_back(num1 % 2);
            num1 /= 2;
        }
        int m = arr.size();
        if (n >= m) {
            return (1 << n) - 1;
        } else {
            int res = 0;
            for (int i = m - 1;  n > 0 && i >= 0; i--) {
                if (arr[i] == 1) {
                    res += (1 << i);
                    n--;
                }
            }
            for (int i = 0; n > 0 && i < m; i++) {
                if (arr[i] == 0) {
                    res += (1 << i);
                    n--;
                }
            }
            return res;
        }
    }
};

6195. 对字母串可执行的最大删除数

题目

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：

删除 整个字符串 s ，或者
对于满足 1 <= i <= s.length / 2 的任意i，如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ，删除 前 i 个字母。
例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到 "abc" ，因为 s 的前两个字母和接下来的两个字母都等于 "ab" 。

返回删除 s 所需的最大操作数。

示例 1：

输入：s = "abcabcdabc"
输出：2
解释：
- 删除前 3 个字母（"abc"），因为它们和接下来 3 个字母相等。现在，s = "abcdabc"。
- 删除全部字母。
一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。
注意，在第二步操作中无法再次删除 "abc" ，因为 "abc" 的下一次出现并不是位于接下来的 3 个字母。

示例 2：

输入：s = "aaabaab"
输出：4
解释：
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "aabaab"。
- 删除前 3 个字母（"aab"），因为它们和接下来 3 个字母相等。现在，s = "aab"。 
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "ab"。
- 删除全部字母。
一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。

示例 3：

输入：s = "aaaaa"
输出：5
解释：在每一步操作中，都可以仅删除 s 的第一个字母。

提示：

• 1 <= s.length <= 4000
• s 仅由小写英文字母组成

地址

https://leetcode.cn/problems/maximum-deletions-on-a-string/description/

题意

动态规划

思路

1. 首先我们需要求的是对于两个字符串的匹配相等问题，我们可以用动态规划或者 krap算法均可，来计算两个相同长度的字符串的匹配相等问题，设 $lcp[i][j]$ 表示 $i,j$ 开始可以匹配的最长长度。

• 动态规划的递推公式为 $$lcp[i][j] = lcp[i+1][j+1], \quad if s[i] = s[j]$$
  上述的过程我们可以进行预处理，比较简单。

2. 我们设 $dp[i]$ 表示 $s$ 从 $i$ 处开始消除所需要的最大操作步数，我们从后往前遍历，假设 $s[i,\cdots, i + k - 1] = s[i + k,\cdots, i + 2k - 1]$，此时我们知道可以从 $k$ 处断开消减前 $k$ 个字符，所以可以得到递推公式如下:
   $$
   dp[i] = \max(dp[i], dp[i + k] + 1)
   $$
3. 复杂度分析：

• 时间复杂度：$O(n^2)$，其中 $n$ 表示字符串的长度。
• 空间复杂度：$O(n^2)$，其中 $n$ 表示字符串的长度。

代码

1. 解法 $1$:

   class Solution { public: int deleteString(string s) { int base = 31; int mod = 1e9 + 7; int n = s.size(); vector<vector<bool>> same(n + 1, vector<bool>(n + 1, false)); vector<long long> arr(n + 1, 1); for (int i = 0; i < n; i++) { arr[i + 1] = (arr[i] * base) % mod; } for (int i = 0; i < n; i++) { long long h = 0; vector<long long> cnt; for (int j = i; j < n; j++) { h = (h * base % mod + (s[j] - 'a')) % mod; cnt.emplace_back(h); if ((j - i + 1) % 2 == 0) { int k = (j - i + 1) / 2; long long h1 = cnt[k - 1] * arr[k] % mod; long long h2 = (cnt.back() - cnt[k - 1] * arr[k] % mod + mod) * arr[k] % mod; if (h1 == h2) { same[i + 1][k] = true; } } } } vector<int> dp(n + 1, -1); dp[0] = 0; for (int i = 1; i <= n; i++) { if (dp[i - 1] >= 0) { for(int j = 1; i + j * 2 - 1 <= n; j++) { if (same[i][j]) { dp[i + j - 1] = max(dp[i + j - 1], dp[i - 1] + 1); } } dp[n] = max(dp[n], dp[i - 1] + 1); } } return dp[n]; } };

2. 解法 $2$:

   class Solution { public: int deleteString(string s) { int n = s.size(); vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0)); for (int i = n - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { if (s[i] == s[j]) { lcp[i][j] = lcp[i + 1][j + 1] + 1; } } } vector<int> dp(n + 1, 1); dp[n] = 0; for (int i = n - 1; i >= 0; i--) { for (int j = 1; j <= (n - i) / 2; j++) { if (lcp[i][i + j] >= j) { dp[i] = max(dp[i], dp[i + j] + 1); } } } return dp[0]; } };

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿