美团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;
}
类似资料：