美团3.25，后台开发笔试
建议其他厂向美团学习
// 1 模拟栈
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
bool check(vector<int> &in, vector<int> &out, int n)
{
stack<int> st;
int pos = 0;
for (int i = 0; i < n; ++i)
{
st.push(in[i]);
while (!st.empty() && pos < n && st.top() == out[pos])
{
pos++;
st.pop();
}
}
return st.empty();
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> in(n);
vector<int> out(n);
for (int i = 0; i < n; ++i)
cin >> in[i];
for (int i = 0; i < n; ++i)
cin >> out[i];
if (check(in, out, n))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
// 2 打家劫舍拓展
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> candy(n);
for (int i = 0; i < n; ++i)
cin >> candy[i];
if (n <= 3)
cout << max({candy[0], candy[1], candy[2]});
else
{
int ans = max({candy[0], candy[1], candy[2]});
vector<int> dp0(n, 0), dp1(n, 0);
dp0[0] = 0;
dp1[0] = candy[0];
dp0[1] = max(dp0[0], dp1[0]);
dp1[1] = candy[1];
dp0[2] = max(dp0[1], dp1[1]);
dp1[2] = candy[2];
for (int i = 3; i < n; ++i)
{
dp0[i] = max(dp0[i - 1], dp1[i - 1]);
dp1[i] = max(dp1[i - 3] + candy[i], dp0[i - 3] + candy[i]);
ans = max({ans, dp1[i], dp0[i]});
}
cout << ans << endl;
}
return 0;
}
// 3 贪心+二分
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int biSearch(vector<long long> &weights, long long q, int n)
{
int left = 0, right = n - 1;
if (weights[n - 1] <= q)
return n;
if (weights[0] > q)
return 0;
int mid;
while (left < right)
{
mid = (left + right) / 2;
if (weights[mid] == q)
return mid + 1;
else if (weights[mid] > q)
right = mid - 1;
else
left = mid + 1;
}
if (weights[left] > q)
return left;
else
return left + 1;
}
int main()
{
int n, m;
cin >> n >> m;
vector<int> chlt(n);
vector<long long> weight(n);
vector<long long> questions(m);
vector<int> res(m);
for (int i = 0; i < n; ++i)
cin >> chlt[i];
for (int i = 0; i < m; ++i)
cin >> questions[i];
sort(chlt.begin(), chlt.end());
for (int i = 0; i < n; ++i)
{
if (i == 0)
weight[i] = chlt[i] * chlt[i];
else
weight[i] = weight[i - 1] + chlt[i] * chlt[i];
}
for (int i = 0; i < m; ++i)
{
res[i] = biSearch(weight, questions[i], n);
}
for (int i = 0; i < m; ++i)
{
if (i == 0)
cout << res[i];
else
cout << " " << res[i];
}
cout << endl;
return 0;
}
// 4 简单字符串split
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
string s;
cin >> s;
int n;
cin >> n;
int begin = 0;
unordered_map<string, string> umap;
while (begin < s.size())
{
int eq = begin;
while (s[eq] != '=')
eq++;
string key = s.substr(begin, eq - begin);
int v = eq + 1;
while (s[v] != ';')
v++;
string val = s.substr(eq + 1, v - eq - 1);
umap[key] = val;
begin = v + 1;
}
while (n--)
{
string q;
cin >> q;
if (umap.find(q) != umap.end())
cout << umap[q] << endl;
else
cout << "EMPTY" << endl;
}
return 0;
}
// 5 lc打家劫舍拓展（第二题拓展）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> candy(n);
vector<vector<int>> dp0(n, vector<int>(k + 1));
vector<vector<int>> dp1(n, vector<int>(k + 1));
for (int i = 0; i < n; ++i)
{
cin >> candy[i];
}
int ans = 0;
dp0[0][0] = 0;
dp1[0][0] = candy[0];
for (int i = 1; i < n; ++i)
{
for (int j = 0; j <= k && j <= i; ++j)
{
dp0[i][j] = max(dp1[i - 1][j], dp0[i - 1][j]);
dp1[i][j] = dp0[i - 1][j] + candy[i];
if (j >= 1)
dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - 1] + candy[i]);
ans = max({ans, dp0[i][j], dp1[i][j]});
}
// cout << ans << endl;
}
cout << ans << endl;
return 0;
}
