今日刷题汇总 - day008

1、求最小公倍数

1.1、题目

1.2、思路

读完题知道，需要完成求两个正整数的最小公倍数。那么A和B的最⼩公倍数的公式 = A*B/两者的最⼤公约数。而最⼤公约数：可以使用辗转相除法、穷举法、更相减损法和质因数分解法等。这里就使用最常用的穷举法和辗转相除法即可。接下来，就是程序实现。

1.3、程序实现 – 穷举法

穷举法就是如果大数可以整除小数，那么最大公约数为小数。如果不能整除小数，那么这两个数就按大到小依次对比小数小的数求余，遇到都能够整除的，就是最大公约数。

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    int min = a>b ? a : b;
    int ret = 0;
    for(int i = 1;i <= min;i++)
    {
        if(a%i == 0 && b%i == 0)
            ret = i;
    }
    cout << a*b/ret << endl;
    return 0;
}

1.2、程序实现 – 辗转相除法

辗转相除法就是用a对b求余，若余数为0，则除数b为最大公约数。若余数不为0，将此余数r作为新的除数，b作为新的被除数，重新求余，直到余数为0为止。此时的最大公约数为除数。

#include <iostream>
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;
    return 0;
}

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

2.1、题目

2.2、思路

读完题，明白，让我们求无序数组中的连续序列的最大长度，并且连续可与位置无关。刚读完题就联想到感觉跟之前的字符串中找出连续最长的数字串思路类似的计数而已。那么这里先进行可以采用sort数组的排序，然后利用变量countlen记录更新长度，利用maxcount保留最大长度并最后返回，然后遍历数组，当相邻的元素是连续的就更新countlen长度，如果相邻的数值相同则越过继续判断下一位元素即可，最后遍历结束返回最大值maxcount，其中涉及一些细节处理，接下来，就是程序实现。

2.3、程序实现

首先，按照思路sort排序数组和定义好变量，然后写好遍历框架，然后只要响铃元素是连续或者相等的元素，则继续j++遍历，否则break即可，直到len结束while，进入下次循环前需要更新j = i+1重新从新的连续位置遍历，countlen = 1来重新计入countlen 大小其中注意无需i++，可以直接越过countlen。所以也可以得出，不需要每次都i++，可以直接越过countlen，避免重复判断比较操作。最后，得到的maxcount就是最大长度。

class Solution {
public:
    int MLS(vector<int>& arr)
    {
        sort(arr.begin(),arr.end());
        int len = arr.size();
        int j = 0;
        int countlen = 1;
        int maxcount = 0;
        for(int i = 0;i < len; i+=countlen)
        {
            j = i + 1;
            countlen = 1;
            while(j < len)
            {
                if(arr[j] - arr[j-1] == 1)
                {
                    countlen++;
                    j++;
                }
                else if(arr[j] - arr[j-1] == 0)
                {
                    j++;
                }
                else
                {
                    break;
                }
            }
            maxcount = max(maxcount , countlen);
        }
        return maxcount;
    }
};

3、字母收集

3.1、题目

3.2、思路

读完题，知道让实现在n*m矩阵中，拼接或者搜索或者贪心收集，按照一定的规则走最优的路径使得获得的分数最多。那么这里使用推导dp动态规划思路，只要使用dp就得确定dp[i]动态表示和动态转移方程。由题目规则很容易想到：
dp[i][j]表示：到第i行j列的最大分数和；
那么推导状态转移方程就是：dp[i][j] = 由左边dp[i][j-1]或上方dp[i-1][j]，再加上其分数得到；
即： dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + score；值得注意的是，此题是从下标1开始的。那么接下来，就是程序实现。

3.3、程序实现

首先，按照题目要求和思路定义字符二维数组和dp数组，接着输入n*m二维数组，下标从1开始的。然后，定义score分数变量，接着遍历二维数组，判断并匹配字符是否为加分字符，累加到dp[i][j]中，最后输出dp[n][m]即可。

#include <iostream>
using namespace std;

const int N = 501;
char ch[N][N];
int dp[N][N];

int main() {
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            cin >> ch[i][j];
        }
    }

    int score = 0;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(ch[i][j] == 'l')
                score = 4;
            else if(ch[i][j] == 'o')
                score = 3;
            else if(ch[i][j] == 'v')
                score = 2;
            else if(ch[i][j] == 'e')
                score = 1;
            else
                score = 0;
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + score;
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

4、题目链接

求最小公倍数
数组中的最长连续子序列
字母收集