leetcode contest 312
leetcode contest 312
前三题的题目也确实太水了。
6192. 公因子的数目
题目
给你两个正整数 a 和 b ，返回 a 和b 的 公 因子的数目。
如果 x 可以同时整除 a 和b ，则认为 x 是 a和 b 的一个 公因子 。
示例 1：1
2
3输入：a = 12, b = 6
输出：4
解释：12 和 6 的公因子是 1、2、3、6 。
示例 2：1
2
3输入：a = 25, b = 30
输出：2
解释：25 和 30 的公因子是 1、5 。
提示：
1 <= a, b <= 1000
地址
https://leetcode.cn/problems/number-of-common-factors/
题意
模拟
思路
- 因为数据量实在太小，直接暴力即可。
- 复杂度分析：
- 时间复杂度：$O(n)$，其中 $n$ 给定的数的大小。
- 空间复杂度：$O(1)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13class 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：1
2
3输入：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：1
2
3输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：35
解释：上图中的单元格表示元素总和最大的沙漏：1 + 2 + 3 + 5 + 7 + 8 + 9 = 35 。
提示：
m == grid.lengthn == grid[i].length3 <= m, n <= 1500 <= grid[i][j] <= 106
地址
https://leetcode.cn/problems/maximum-sum-of-an-hourglass/
题意
枚举中心
思路
- 设矩阵的行列分别为 $m,n$，根据题意我们枚举所有可能的中心位置 $x$，可以知道以 $(x,y)$ 为中心的位置的沙漏元素和为 $grid[x][y] + \sum_{i = y - 1}^{y+1} \limits (grid[x-1][i] + grid[x+1][i])$，我们依次求出可能的沙漏值即可。
- 复杂度分析：
1 | |
6194. 最小 XOR
题目
给你两个正整数 num1 和 num2 ，找出满足下述条件的整数 x ：
x的置位数和num2相同，且x XOR num1的值 最小
注意XOR是按位异或运算。
返回整数 x 。题目保证，对于生成的测试用例， x 是 唯一确定 的。
整数的 置位数 是其二进制表示中 1 的数目。
示例 1：1
2
3
4
5输入：num1 = 3, num2 = 5
输出：3
解释：
num1 和 num2 的二进制表示分别是 0011 和 0101 。
整数 3 的置位数与 num2 相同，且 3 XOR 3 = 0 是最小的。
示例 2：1
2
3
4
5输入：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/
题意
贪心
思路
- 典型的贪心熟路，设 $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$，这样保证形成的数最小；
- 复杂度分析
- 时间复杂度：时间复杂度为 $O(\log (nums1) + \log (nums2))$，$nums1,nums2$ 为给定的数。
- 空间复杂度：时间复杂度为 $O(\log (nums1))$，$nums1,nums2$ 为给定的数。
代码
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
27
28
29
30class 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：1
2
3
4
5
6
7输入：s = "abcabcdabc"
输出：2
解释：
- 删除前 3 个字母（"abc"），因为它们和接下来 3 个字母相等。现在，s = "abcdabc"。
- 删除全部字母。
一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。
注意，在第二步操作中无法再次删除 "abc" ，因为 "abc" 的下一次出现并不是位于接下来的 3 个字母。
示例 2：1
2
3
4
5
6
7
8输入：s = "aaabaab"
输出：4
解释：
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "aabaab"。
- 删除前 3 个字母（"aab"），因为它们和接下来 3 个字母相等。现在，s = "aab"。
- 删除第一个字母（"a"），因为它和接下来的字母相等。现在，s = "ab"。
- 删除全部字母。
一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。
示例 3：1
2
3输入：s = "aaaaa"
输出：5
解释：在每一步操作中，都可以仅删除 s 的第一个字母。
提示：
1 <= s.length <= 4000s仅由小写英文字母组成
地址
https://leetcode.cn/problems/maximum-deletions-on-a-string/description/
题意
动态规划
思路
- 首先我们需要求的是对于两个字符串的匹配相等问题，我们可以用动态规划或者
krap算法均可，来计算两个相同长度的字符串的匹配相等问题，设 $lcp[i][j]$ 表示 $i,j$ 开始可以匹配的最长长度。
- 动态规划的递推公式为
上述的过程我们可以进行预处理，比较简单。
- 我们设 $dp[i]$ 表示 $s$ 从 $i$ 处开始消除所需要的最大操作步数，我们从后往前遍历，假设 $s[i,\cdots, i + k - 1] = s[i + k,\cdots, i + 2k - 1]$，此时我们知道可以从 $k$ 处断开消减前 $k$ 个字符，所以可以得到递推公式如下:
- 复杂度分析：
- 时间复杂度：$O(n^2)$，其中 $n$ 表示字符串的长度。
- 空间复杂度：$O(n^2)$，其中 $n$ 表示字符串的长度。
代码
- 解法 $1$:
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class 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$:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class 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
- 关注我的微信公众号: 公务程序猿
