48days强训——day8
第一题：求最小公倍数
描述 对于给定的两个正整数 a,ba,b，它们的最小公倍数 lcm(a,b)lcm(a,b) 是指能同时被 aa 和 bb 整除的最小正整数。 求解 lcm(a,b)lcm(a,b)。 输入描述： 在一行上输入两个整数 a,b(1≦a,b≦105)a,b(1≦a,b≦105)。 输出描述： 输出一个整数，表示 lcm(a,b)lcm(a,b)。 示例1 输入： 5 7 输出： 35 示例2 输入： 2 4 输出： 4
题解： 最小公倍数（LCM）可以通过最大公约数（GCD）计算：LCM(a,b) = a×b / GCD(a,b)。使用欧几里得算法求GCD，即递归地取模直到余数为0。时间复杂度为O(log min(a,b))，适用于大数计算。
代码：
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a % b);
}
int main()
{
int a,b;
cin >> a>>b;
cout << (a*b/gcd(a,b))<<endl;
}第二题：数组中的最长连续子序列
描述 给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数） 数据范围： 1≤n≤1051≤n≤105，数组中的值满足 1≤val≤1081≤val≤108 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn) 示例1 输入： [100,4,200,1,3,2] 返回值： 4 示例2 输入： [1,1,1] 返回值： 1 备注： 1≤n≤1051≤n≤105 1≤arri≤1081≤arri≤108
题解：排序+模拟，且需要处理，数字相同的情况。
代码：
class Solution
{
public:
int MLS(vector<int>& arr)
{
sort(arr.begin(), arr.end());
int ret = 0;
for(int i = 0; i < arr.size(); )
{
int j = i+1,count =1;
while(j < arr.size())
{
if(arr[j]- arr[j-1] == 1)
{
count++;
j++;
}
else if(arr[j] == arr[j-1]) j++;
else break;
}
ret = max(ret,count);
i = j;
}
return ret;
}
};第三题：字母收集
题目描述： 有一个 n∗mn∗m 的矩形方阵，每个格子上面写了一个小写字母。 小红站在矩形的左上角，她每次可以向右或者向下走，走到某个格子上就可以收集这个格子的字母。 小红非常喜欢 "love" 这四个字母。她拿到一个 l 字母可以得 4 分，拿到一个 o 字母可以得 3 分，拿到一个 v 字母可以得 2 分，拿到一个 e 字母可以得 1 分。 她想知道，在最优的选择一条路径的情况下，她最多能获取多少分？ 输入描述： 1≤n,m≤5001≤n,m≤500 接下来的 nn 行 每行一个长度为 mm 的、仅有小写字母构成的字符串，代表矩形方阵。 输出描述： 小红最大可能的得分。 示例1 输入： 3 2 ab cd ef 输出： 1 说明： 选择下、下、右）这条路径即可，可以收集到 acef 这四个字母各一次，获得 0+0+1+0=1 分。 示例2 输入： 2 3 lle ove 输出： 11
题解：动态规划问题。从左上到右下，每次只能右移或下移，统计路径中love的总分。每个位置的最大得分由其左、上邻格的最大值加上当前字母得分决定。最终右下角的值即为答案。
代码：
#include <bits/stdc++.h>
using namespace std;
char nums[501][501];
int dp[501][501];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> nums[i][j];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
int t = 0;
if(nums[i][j] == 'l') t = 4;
else if(nums[i][j] == 'o') t = 3;
else if(nums[i][j] == 'v') t = 2;
else if(nums[i][j] == 'e') t = 1;
dp[i][j] = max(dp[i-1][j],dp[i][j-1])+t;
}
}
cout << dp[n][m] << endl;
return 0;
}腾讯云开发者
