目录

1.求最小公倍数

 2.数组中的最⻓连续⼦序列

3.字母收集

---

1.求最小公倍数

链接

这就是一道普通的数学题。

最大公倍数 = A * B / A 与 B之间的最大公约数。

最大公约数求法：辗转相除法(或者可以用<numeric>头文件中的gcd)

#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.数组中的最⻓连续⼦序列

链接

因为题目要求值连续，但是位置可以不连续，于是我就想到了可以先去排序，然后采用类似滑动窗口的思想去遍历所有长度，边遍历边更新len。

代码：

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

3.字母收集

链接

我看到这个方格子直接就想去DFS了，简直无语了。DFS半天，给自己都DFS懵逼了。

其实这题正解是dp（动态规划）

而且是很基本的动态规划，只比斐波那契难一点点。

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

从一开始存入图，方便初始化。