美团25日实习软开笔试

##有出错的地方麻烦各位大佬指教！！！

美团C++转正实习

时间:2023/3/25
完成情况：3/5
时长：2h
自我总结：第一次使用ACM模式，输入输出上不熟悉花了较长时间

五道编程题

==第一道：==验证出入栈顺序有效性，leetcode原题，当时文字太多，没有静下心好好审题直接跳过了，血亏

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    int s1 = pushed.size();
    stack<int> sta;
    sta.push(pushed[0]);
    int i = 1;
    int j = 0;
    bool res;
    while (!sta.empty()) {
        if (sta.top() != popped[j]) {
            if (i >= s1) {
                return  false;
            }
            sta.push(pushed[i]);
            i++;

        }
        else {
            sta.pop();
            j++;
            if (sta.empty() && i < s1) {
                sta.push(pushed[i]);
                i++;
            }
        }
    }
    return true;

}

int main() {
    bool res;
    vector<int> pushed;
    vector<int> poped;
    int n;
    cin >> n;
    int num1;
    while (n > 0 && cin >> num1) {
        pushed.push_back(num1);
        n--;
    }
    int m;
    cin >> m;
    while (m > 0 && cin >> num1) {
        poped.push_back(num1);
        m--;
    }
    res = validateStackSequences(pushed, poped);
    cout << res << endl;

    return 0;
}

==第二道：== 动态规划，跟leetcode打家劫舍差不多，要求选了a[i],就不能选a[i-1],a[i -2],a[i+1],a[i +2], 给你一个数组代表a[i]的值，求怎么选最大。
dp[i]代表数组长度i所能选到的最大值
状态转移方程：dp[i] = max(dp[i-1], dp[i -3] + a[i])

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

int choice(vector<int>& a) {
    int len = a.size();
    vector<int> dp(len);
    dp[0] = a[0];
    if (len >= 2) {
        dp[1] = max(a[0], a[1]);
        if (len >= 3) {
            dp[2] = max( dp[1], a[2]);
        }
    }
    for (int i = 3; i < len; i++) {
        int tmp = dp[i - 3] + a[i];
        dp[i] = max(dp[i - 1], tmp);
    }
    return dp[len - 1];
}

int main() {
    int res;
    vector<int> a;
    int n;
    cin >> n;
    int num1;
    while (n > 0 && cin >> num1) {
        a.push_back(num1);
        n--;
    }
    res = choice(a);

    cout << res << endl;

    return 0;
}

==第三道==： 0-1背包问题，n块巧克力板，边长为a[i], 重量为a[i]*a[i], m 个背包，可以装重量为b[i]，求每个背包最多可以装多少
思路：可以对巧克力板按重量从小到大排序，前缀和即可

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

int large(vector<int>& a, int b) {
    int sum = 0;
    int len = a.size();
    int i;
    for (i = 0; i < len; i++) {
        sum += a[i];
        if (sum > b) {
            break;
        }
    }
    return i;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a, b;
    int ins;
    while (n > 0 && cin >> ins) {
        a.push_back(ins * ins);
        n--;
    }
    while (m > 0 && cin >> ins) {
        b.push_back(ins);
        m--;
    }
    sort(a.begin(), a.end());
    for (int tmp : b) {
        cout << large(a, tmp)<< " ";
    }
    cout << endl;

    return 0;
}

==第四道：==字符分割，如给你一串字符“path=/chat.openai.com, language=c++, path=baidu.com", 输入 2 path language，输出 baidu.com c++
使用unordered_map

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>

using namespace std;


int main() {
    string str;
    getline(cin, str);
    unordered_map<string, string> mmap;
    //字符分割
    for (int i = 0; i < str.size(); i++) {
        int start = i;
        while (start < str.size() && str[start] != '=') {
            start++;
        }
        string str2 = str.substr(i, start - i);
        int start2 = start + 1;
        while (start2 < str.size() && str[start2] != ',') {
            start2++;
        }
        string str3 = str.substr(start + 1 , start2 - start - 1);
        i = start2;
        //此处说相同的key取后者的value，应该直接替代是没有问题的
        mmap[str2] = str3;
    }
    //输入验证
    int n;
    cin >> n;
    string str4;
    vector<string> vec;
    while (n > 0 && cin >> str4) {
        vec.push_back(str4);
        n--;
    }
    for (string& strTmp : vec) {
        if (mmap.count(strTmp) >= 1) {
            cout << mmap[strTmp] << endl;
        }
        else {
            cout << "EMPTY" << endl;
        }
    }
    return 0;
}

==第五道：==给你一个每一天糖果的美味值数组，只能隔天吃，但也可以反悔，有K次反悔机会
思路：先用打家劫舍的方法，然后对对没有选的取k个最大值

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<queue>

using namespace std;
int maxTaste(int k, vector<int>& vec) {
    int len = vec.size();
    vector<int> dp(len);
    dp[0] = vec[0];
    if (len == 1) {
        return dp[0];
    }
    vector<bool> used(len, false);
    if (len >= 2) {
        dp[1] = max(dp[0], vec[1]);
        if (len == 2) {
            if (k > 0) {
                return vec[0] + vec[1];
            }
            else {
                return dp[1];
            }
        }
    }
    for (int i = 2; i < len; i++) {
        dp[i] = max(dp[i - 2] + vec[i], dp[i - 1]);
    }
   //判断最后一个选了没
    bool jus;
    if (dp[len - 3] + vec[len - 1] > dp[len - 2]) {
        jus = true;
    }
    else {
        jus = false;
    }
    priority_queue<int, vector<int>, less<int>> pq;
    if (!jus) {
        for (int i = len - 1; i > 0; i = i - 2) {
            pq.push(vec[i]);
        }
    }
    else {
        for (int i = len - 2; i > 0; i = i - 2) {
            pq.push(vec[i]);
        }
    }
    int res = dp[len - 1];
    for (int i = 0; i < k; i++) {
        res += pq.top();
        pq.pop();
    }
    return res;



}

int main() {
    //反悔次数
    int k;
    cin >> k;
    //输入美味值
    int n;  //天数
    cin >> n;
    vector<int> vec;
    int  num;
    while (n > 0 && cin >> num) {
        vec.push_back(num);
        n--;
    }
    cout << maxTaste(k, vec) << endl;
    return 0;
}

#美团笔试#