给你两个正整数 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 。
数据范围比较小,直接暴力即可。
class Solution {
public:
int commonFactors(int a, int b) {
int n = 0;
for(int i = 1;i <= min(a, b);i++){
if(a %i == 0 && b % i == 0)n++;
}
return n;
}
};
给你一个大小为 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
暴力
class Solution {
public:
int maxSum(vector<vector<int>>& grid) {
int maxn = INT_MIN;
int ia[] = {-1, -1, -1, 0, 1, 1,1};
int ja[] = {-1, 0, 1, 0, -1, 0, 1};
for(int i = 1;i < grid.size() - 1;i++){
for(int j = 1;j < grid[0].size() - 1;j++){
int cmaxn = 0;
for(int t = 0;t <7;t++){
cmaxn += grid[i + ia[t]][j + ja[t]];
}
maxn = max(maxn, cmaxn);
}
}
return maxn;
}
};
给你两个正整数 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 是最小的。
提示:
挺有意思的一道位运算贪心题,首先计算num2的二进制中1的bit位数,对应x的bit为1的位数,然后要和num1异或值最小,那么就让x从高位往低位按照num1的1bit位填1,如果num2的1bit位数比num1更多,多的就让x从低位往高位把0bit填1,最后的x即为结果。
例如num1 = 8, num2 = 5:
num2的二进制为:0101
两个1所以求得x的1bit位有2个
num1的二进制为:1000
x从高位往前对应num1填两个1,但num1只有1个1bit,所以多余的从低位往前填,结果为:
x 二进制为: 1001
,所以输出十进制9。
class Solution {
public:
int minimizeXor(int num1, int num2) {
int bn = 0;
for(int i = 0;i < 32;i++){
if((num2 >> i) & 1)bn++;
}
int num = 0;
for(int i = 31;i >= 0 && bn > 0;i--){
if((num1 >> i) & 1){
num += 1 << i;
bn--;
}
}
for(int i = 0;i < 32 && bn > 0;i++){
if(((num >> i) & 1) == 0){
bn--;
num += 1 << i;
}
}
return num;
}
};
给你一个仅由小写英文字母组成的字符串 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 的第一个字母。
先找规律,例如:串s为:'abab',对于这个串开头前两个ab和后两个相同,所以可以删除开头ab。 那么串s的最大操作数就为1 + 'ab'子串的最大操作数,所以可以看到这是一个重叠子问题,那么理所当然的可以想到用动态规划来做,设dp[i]为从i开始的子串的最大操作数,dp[0]的值就是我们要求的s的最大操作数。 递推式为: dp[i] = 1 + dp[i+len] if s[i : i+len] == s[i+len : i+2*len] dp[i] = 1 else len为相同串长度,若有多个长度的相同串,dp[i]取最大值。
判断时间复杂度: 从后往前遍历s,对每个i计算dp[i],每次计算dp[i],len取[1, s.size / 2]。 每个dp[i]需要O(n^2),计算n个dp[i]最后为O(n^3),显然超了,所以还需要在判断相同串的方式上进行优化。
我们先计算任意两个子串间最长前缀和以便后续判断相同串,设lcp[i][j]为s[i : ]和s[j : ]的最长前缀和长度,它的递推式就为:
lcp [i] [j] = lcp [i+1] [j+1] + 1 if s[i] == s[j] lcp [i] [j] = 0 else
有了lcp,两个子串是否相同直接看lcp就能得知。 判断时间复杂度: 计算lcp需要O(n^2), 有了lcp计算每个dp[i]需要O(n),计算n个dp[i]就为O(n^2),所以最终的时间复杂度就为O(n^2)。
class Solution {
public:
int deleteString(string s) {
int dp[4005] = {}; //[i, n-1]串最大删除数
//lcp[i][j] s[i]与s[j]的最长前缀和
vector<vector<int>> lcp(s.size() + 5, vector<int>(s.size() + 5, 0));
for(int i = s.size() - 1;i >= 0;i--){
for(int j = s.size() - 1;j > i;j--){
lcp[i][j] = s[i] == s[j] ? lcp[i+1][j+1]+1 : 0;
}
}
auto getmaxn = [&](int i)->int{
int maxn = 0;
int len = (s.size() - i) / 2;
for(;len >= 1;len--){
bool flag = true;
if(lcp[i][i + len] >= len)
maxn = max(maxn, dp[i + len] + 1);
}
return maxn;
};
for(int i = s.size() - 1;i >= 0;i--){
dp[i] = max(getmaxn(i), 1);
}
return dp[0];
}
};
时间复杂度:O(n^2) 空间复杂度:O(n^2)
我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=1ag9f3xrw54xw