一、求最小公倍數
題目解析
題目很簡單，給定兩個數
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];}}//初始化dpfor(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
