C++笔试强训day8

目录

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;
}

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