写一下2024年美团秋招第一场笔试算法题解，先贴个测评和题目链接美团2024秋招第一场笔试，还是比较简单的，前两题都是模拟，其中第二题涉及点思维，第三题笔者看到有牛友用持久化线段树和dp做的，但是我还不咋会主席树哈哈，于是给大家提供一种很巧妙的模拟做法，希望可以对大家有所帮助~~~(ak美团笔试题就可以去美团送外卖了)——不说了，我快超时了-----
最近开始开始重开java后端开发了，兜兜转转还是java选手，我打算以后多更新大厂算法笔试的题解~~~~欢迎大家讨论交流和支持，蟹蟹~~~
目录
A题
题面
思路分析
代码实现
B题
题面
思路分析
代码实现
C题
题面
思路分析
代码实现
A题
题面
思路分析
直接模拟就行，判断数字可以用isdigit函数，判断字母可以用alpha函数。
代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
#define x first
#define y second
using namespace std;
int f(string s)
{
int cnt1 = 0;
int cnt2 = 0;
int cnt3 = 0;
//int flag = 0;
for(int i = 1; i < s.size(); i++)
{
if(isdigit(s[i])) cnt1 ++;
else if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z')) cnt2 ++;
else cnt3++;
}
if(cnt1 == s.size() - 1) return 1;
else if(cnt2 == s.size() - 1) return 2;
else if(cnt3 == 0) return 3;
else return 4;
}
void solve()
{
string s;
cin >> s;
if(isdigit(s[0]) && f(s) == 2) cout << "special" << endl;
else if(isalpha(s[0]) && f(s) == 1) cout << "standard" << endl;
else if(isalpha(s[0]) && f(s) == 3) cout << "mix" << endl;
else cout << "invalid" << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t -- ) solve();
return 0;
}B题
题面
思路分析
做这题最开始笔者想歪了，开个map把每个字符串数量统计进去，然后开了个字符串数组还对字符串排个序 ，但是发现这样对解这道题一点用没有，于是仔细看看题目，我们梳理一下题意，题目让我们求最少和最多比较次数，首先我们应该明白最少操作次数为1，第二点重要的是一定是从比小于正确密码长度的字符串开始比较的，如果发现不匹配则再次碰到这样的字符串我们就不再比较，于是我们有如下思路：
1.开一个哈希表set，记录有没有添加过该密码，至少需要尝试1次
2.如果输入的密码长度小于真实密码且未出现过，一定会被尝试，两个都加一次
3. //如果输入的密码长度等于真实密码且未出现过，最多的加一次就行了，因为算最少我们一次就能匹配成功，所以x不用加。
下面我们看看完整代码就明白了——
代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <cstring>
#include <string>
#include <vector>
#include <unordered_set>
#define int long long
#define x first
#define y second
using namespace std;
void solve()
{
int n;
cin >> n;
string str;
cin >> str;
unordered_set<string> st;//记录有没有添加过该密码
int x = 1;//至少需要尝试1次
int y = 0;
while(n -- )
{
string s;
cin >> s;
//如果输入的密码长度小于真实密码且未出现过，一定会被尝试，两个都加一次
if(s.size() < str.size() && st.count(s) == 0)
{
x++;
y++;
st.insert(s);
}
//如果输入的密码长度等于真实密码且未出现过，最多的加一次就行了
if(s.size() == str.size() && st.count(s) == 0)
{
y++;
st.insert(s);
}
}
cout << x << " " << y << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t = 1;
while(t -- ) solve();
return 0;
}C题
题面
思路分析
这题笔者也不知道本题出题的std是什么，应该很多种做法，看到了可持久化线段树，dp等做法，但是大家好像大多还是模拟来做的，这里贴一种巧妙的做法，妙在反着去判断当前数组中不包含的最小非负整数，利用一个while循环和一个set容器，我们for循环倒着遍历，依次删除前j个元素，然后再将剩下的元素按照MEX(a) * k删除，MEX(a)就用set不断地insert剩下的每个元素，从最开始ans = 0维护，如果set里存入了后面的数，我们将ans++即可，最后跳出循环的ans即为剩下数组里不存在的最小非负整数，我在代码中把样例的x,j,k,ans都输出了，方便理解，仔细看看代码其实也就明白了，完成了上面操作，我们不断求花费值然后更新最小值就行了——
代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <unordered_set>
#define int long long
#define x first
#define y second
using namespace std;
void solve()
{
int n,k,x;
cin >> n >> k >> x;
vector<int> vc(n);
set<int> st;
for(int i = 0; i < n; i++) cin >> vc[i];
int minx = x * n; // 依次删除第一个元素
int ans = 0;
//反着去判断当前数组中不包含的最小非负整数
for(int j = n - 1; j >= 0; j--)
{
st.insert(vc[j]);
while(st.count(ans))
{
ans++;
}
//依次删除前j个元素再将剩下的元素按照MEX(a) * k删除
//cout << x << " " << j << " " << k << " " << ans << endl;
int p = x * j + k * ans;
//cout << p << endl;
minx = min(minx , p);
}
cout << minx << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t -- ) solve();
return 0;
}
/*
input:
1
6 3 3
4 5 2 3 1 0
output:
3 5 3 1
18
3 4 3 2
18
3 3 3 2
15
3 2 3 4
18
3 1 3 4
15
3 0 3 6
18
15(最小值)
*/
最后感谢大家的观看，点个赞加关注再走吧~~拜拜喽~
