美团3月25日笔试题目回忆

下面题目内容是根据回忆所写。

第一题：

给出一个数字1-n的入栈顺序in[]和出栈顺序out[]，问这个出入栈顺序是不是合法的。

example

in：1 2 3

out: 1 2 3

合法，每个元素入栈之后立刻出栈即可

example

in: 1 2 3

out 3 2 1

合法，全部入栈之后再全部出栈

example

in: 1 2 3

out: 3 1 2

不合法。

思路：用一个stack按顺序入栈，同时维护一个指针ptr_out表明按照题目的给出的out数组下一个应该出栈的是哪个元素。按顺序讲in元素入栈，然后如果当前栈顶元素和out[ptr_out]是同一个，那么就将栈顶弹出，同时ptr_out++，直到栈顶和ptr_out指向的原素不同为止。按照这个操作，如果最后能把所有元素都弹出栈并且ptr_out走完了out数组，那么就是是合法的，否则非法。

#include <iostream>
#include <stack>

using namespace std;

int in[50050];
int out[50050];

stack<int> s;

int main() {
    int t;
    int n;
    cin >> t;
    while (t --) {
        cin >> n;
        for (int i = 0; i < n; i ++) {
            cin >> in[i];
        }
        for (int i = 0; i < n; i ++) {
            cin >> out[i];
        }
        int po = 0;
        for (int i = 0; i < n; i ++) {
            s.push(in[i]);
            while (!s.empty() && s.top() == out[po]) {
                s.pop();
                po ++;
            }
        }
        if (s.empty() && po == n) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
        while (!s.empty()) s.pop();
    }
    string s;
    s.
}

第二题：

给出一列数，从中选取若干个，要求所选的任意两个数字的位置至少隔开2个位置，也就是选取了i的话，i-2，i-1，i+1， i+2都不能选。

思路：简单的dp题，用f[i]表示选取只考虑前i项时的最优解是多少。转移方程如下。

f[i] = max(f[i-2], f[i-1], f[i-3] + a[i])；

第三题：

给出一堆巧克力的边长，巧克力的重量是边长的平方。给出若干个询问q，问在重量不超过q的前提下，最多能选多少块巧克力。

思路：贪心，先选小的再选大，因为如果存在一个选择大巧克力的方案的话，必然可以把大巧克力换成比他更小的巧克力达到同样优的解。然后注意题目并不保证给出的巧克力是从小到大的顺序，也不保证询问q是从小到大。于是我们先把巧克力的重量排个序，然后算一下前缀和，之后可以对每个询问做二分查询在线处理，也可以先接受所有的询问，把询问从小到大离线处理。

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
long long a[50050];
long long s[50050];
long long q;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
    }

    sort(a, a + n);

    s[0] = a[0] * a[0];
    for (int i = 1; i < n; i ++) {
        s[i] = s[i - 1] + a[i] * a[i];
    }

    while (m --) {
        cin >> q;
        if (q < s[0]) {
            cout << 0 << ' ';
        } else {
            int l = 0;
            int r = n;
            while (l + 1 < r) {
                int mid = (l + r) / 2;
                if (q >= s[mid]) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            cout << l + 1 << ' ';
        }
    }

}

第四题：

给出一串字符串，形如“key1=val1;key2=val2;key3=val;”，然后给出q个询问，每个询问是一个字符串s，如果s有对应的key，则输出对应的value，如果有多个key对应，则按照最后出现的那一组key value来输出，如果没有对应的则输出“EMPTY”。

思路：字符串处理一下然后使用map或者dict就可以。我不知道我的代码哪里有点问题，只过了18%，有看出来的朋友可以指点我一下吗，谢谢

s = input()
n = input()
if s[-1] == ";":
    s = s[:-1]
pairs = s.split(";")
mapping = {}
for i in range(len(pairs)):
    kv = pairs[i].split("=")
    if len(kv) > 1:
        mapping[kv[0]] = kv[1]

for i in range(int(n)):
    q = input()
    print(mapping.get(q, "EMPTY"))