美团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;

}