【C++】 —— 笔试刷题day_8

一、求最小公倍数

题目解析

题目很简单，给定两个数a和b求它们的最小公倍数。

算法思路

对于求两个数的最小公倍数问题，想必已经非常熟悉了；

在之前学校上课时，记得老师提起过，最小公倍数 = 两个数的乘积 除以最大公约数。

所以我们现在只需要找到两个数的最大公约数，然后就可以求出最小公倍数。

求a和b的最大公约数

• 定义tmp = a%b（这里a > b）
• 循环去执行取%操作，每次把b的值赋给a，tmp的值赋给b，tmp继续取a%b。
• 当tmp的值为0是循环就结束了，此时b的值就是这两个数的最大公约数。

返回结果

求出来了最大公约数，最后返回a*b / 最大公约数即可。

代码实现

#include <iostream>
using namespace std;
//求最大公约数
int gcd(int a, int b) {
    if (a < b) {
        int t = a;
        a = b;
        b = t;
    }
    int tmp = a % b;
    while (tmp) {
        a = b;
        b = tmp;
        tmp = a % b;
    }
    return b;
}
int main() {
    int a, b;
    cin >> a >> b;
    int g = gcd(a, b);
    cout << a* b / g << endl;
    return 0;
}

二、数组中最长的连续子序列

题目解析

本题，题目给定一个无序的数组arr，让我们返回其中最长连续序列的长度（要求数值连续，位置可以不连续）就例如3,5,6,4，只要数值是连续的自然数就可以。

算法思路

对于这道题，暴力解法，枚举出来所以的子序列，找出最长的连续序列，求出来长度即可。

这里不多描述了，回超时。

现在我们在回过去看题目，要求我们找连续序列的长度，(该序列数值是连续的，对位置没有要求)，只要求我们返回长度；

所以我们现在可以先让整个数组有序，让这些连续的数放到一块，这样就方便我们计算长度了。

整体思路如下：

先让数组有序，再利用双指针去寻找连续序列，使用count来记录序列的长度即可

• 排序数组：调用库里面sort即可
• 双指针遍历：i记录连续数组开始位置的下标,j向后遍历；如果j位置数值等于j-1位置数值+1,就count++，继续向后遍历；如果j位置数值等于j-1位置数值，j继续向后遍历；如果j位置数值不等于等于j-1位置数值+1也不等于j-1位置的值，就更新当前结果。
• 更新完结果后，i变道j位置，j从下一个位置继续遍历，直到遍历完整个数组。

这里需要注意：可以存在相等的值，我们count计数的同时也要完成去重操作

代码实现

class Solution {
  public:
    int MLS(vector<int>& arr) {
        //排序数组
        sort(arr.begin(), arr.end());
        int n = arr.size();
        int ret = 0;
        for (int i = 0; i < n;) {
            int j = i + 1;
            int count = 1;
            while (j < n) {
                if (arr[j] - arr[j - 1] == 1) {
                    j++;
                    count++;
                } else if (arr[j] - arr[j - 1] == 0) {
                    j++;
                } else {
                    break;
                }
            }
            if (count > ret)
                ret = count;
            i = j;
        }
        return ret;
    }
};

三、字母收集

题目解析

题目给了一个n*m的字符数组（方阵），让我们选择一条路径，获取最多的分数（得分规则：遇到l字母得4分、遇到o字母得3分、遇到v字母得2分、遇到e字母得1分，其他的字母都不得分）；

在我们选择路径的时候，我们只能从当前节点向右或者向下走。（整个很重要），所以我们就要从1,1位置开始。

算法思路

初次遇见这道题，博主以为是搜索题，就直接使用bfs深度遍历完整个数组，找到当前位置向左和向右走能够获得的分数，然后取其中最大值。

但是，题目中给定范围1<=n,m<=500，深层递归就要执行2^500次，可以说十分恐怖了。

这里直接来看这道题的解题思路：

dp动态规划。

这里我们dp[i][j]就表示走到该位置最大的得分

dp状态转移方程：dp[i][j] = max(dp[i][j-1],dp[i-1][j])+t，其中t表示dp[i][j]位置的得分。

这里为什么呢？

题目上说了，我们只能向下和向右走，所以我们只能从dp[i][j-1]和dp[i-1][j]两个位置走到dp[i][j]；而我们的dp[i][j]表示的就是到当前位置的最大得分，所以，我们就找**dp[i][j-1]和dp[i-1][j]两个位置那个位置的值（也就是到哪个位置的最大得分）两个值中最大的子再加上当前位置得分即可。**

代码实现

这里写代码有几个注意的点：

• 第一个就是我们使用dp时，通常下标从1开始（这里，我们填写dp[1][1]时要用到d[1][0]和dp[0][1]，下标从1开始就不需要先自己填入数据了；因为未初始化未知的值都是0不会影响我们的结果
• 第二个就是这里的填表顺序：我们填dp[i][j]时，需要用到dp[i][j-1]和dp[i-1][j]两个位置的值，所以要从左到右，从上到下依次填写。

#include <iostream>
using namespace std;
const int N = 501;
int dp[N][N] = {0};
char str[N][N];
int main() {
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>str[i][j];
        }
    }
    //初始化dp
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int t = 0;
            if(str[i][j]=='l')  t = 4;
            else if(str[i][j] =='o') t = 3;
            else if(str[i][j] == 'v') t = 2;
            else if(str[i][j] == 'e') t = 1;
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + t;
        }
    }
    cout<<dp[m][n]<<endl;
    return 0;
}

** 到这里本篇文章就结束了，继续加油！**

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws