国庆期间没打
【模拟】公因子的数目
题目
给你两个正整数 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
2
3
4
5
6
7
8
9
10
| class Solution {
public:
int commonFactors(int a, int b) {
int res = 0;
for(int i=1;i<=min(a,b);i++){
if(a%i==0 && b%i==0) res++;
}
return res;
}
};
|
【模拟】沙漏的最大总和
题目
给你一个大小为 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.length
n == grid[i].length
3 <= m, n <= 150
0 <= grid[i][j] <= 10^6
解题思路
简单模拟即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSum(vector<vector<int>>& grid) {
int n = grid.size(),m = grid[0].size();
int res=0;
for(int i=0;i+2<n;i++){
for(int j=0;j+2<m;j++){
int cur = 0;
cur += grid[i][j] + grid[i][j+1] + grid[i][j+2];
cur += grid[i+1][j+1];
cur += grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2];
res = max(res, cur);
}
}
return res;
}
};
|
【位运算+分类讨论】最小 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 是最小的。
|
提示:
解题思路
统计num1的二进制表示中1的个数n,以及num2的二进制表示中1的个数m
注意找的是x,令x XOR num1的最小值为minv
当n=m时,很显然minv=0,此时x为num1
当n>m时,说明num1的前m个高位1应该变成0
当n<m时,说明num1的前m-n个低位0应该变成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
| #include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimizeXor(int num1, int num2) {
int n=0,m=0;
for(int i=0;i<32;i++) if((num1>>i)&1) n++;
for(int i=0;i<32;i++) if((num2>>i)&1) m++;
if(n==m) return num1;
int res = 0;
if(m>n){
res = num1;
for(int i=0,rest=m-n;i<32&&rest;i++){
if((num1>>i)&1) continue;
res ^= (1<<i);
rest--;
}
}else {
for(int i=31,rest=m;i>=0 && rest;i--){
if((num1>>i)&1) {
res ^= (1<<i), rest--;
}
}
}
return res;
}
};
|
【线性DP】对字母串可执行的最大删除数
题目
给你一个仅由小写英文字母组成的字符串 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 <= 4000
s
仅由小写英文字母组成
解题思路
代码
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
| class Solution {
public:
int deleteString(string s) {
int n = s.size();
int lcp[n][n];
//lcp[i][j] s[i..n]与s[j..n]的最长公共前缀
memset(lcp,0,sizeof(lcp));
for(int i=0;i<n;i++){
lcp[n-1][i] = s[n-1]==s[i]?1:0;
lcp[i][n-1] = s[i]==s[n-1]?1:0;
}
for(int i=n-2;i>=0;i--){
for(int j=n-2;j>=0;j--){
if(s[i]==s[j]) lcp[i][j] = max(lcp[i+1][j+1]+1, 1);
else lcp[i][j] = 0;
}
}
vector<int> dp(n,1);//dp[i]: 删除s[i..n]所需的最大操作数
dp[n-1] = 1;
for(int i=n-2;i>=0;i--){
for(int len=1;i+len<n;len++){
if(lcp[i][i+len]>=len){//有至少len个字母相等
dp[i] = max(dp[i], dp[i+len]+1);
}
}
}
// for(int i=0;i<n;i++) cout<<dp[i]<<' ';
return dp[0];
}
};
|