2023.03.25 美团笔试
终于全A了，好不容易，明显感觉这周题目比上周简单很多
1.直接模拟栈就好
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int time;
int len;
int temp;
int left, right;
vector<int> vIn;
vector<int> vOut;
cin >> time;
for (int tt = 0; tt < time; tt++) {
cin >> len;
vIn.clear();
vOut.clear();
for (int oo = 0; oo < len; oo++) {
cin >> temp;
vIn.push_back(temp);
}
for (int oo = 0; oo < len; oo++) {
cin >> temp;
vOut.push_back(temp);
}
left = 0;
right = 0;
stack<int> myStack;
while (right < len && left < len) {
// cout << "left = " << left << endl;
// cout << "right = " << right << endl;
if (vIn[left] == vOut[right]) {
left++;
right++;
} else if ( !myStack.empty() && myStack.top() == vOut[right]) {
right++;
myStack.pop();
} else {
myStack.push( vIn[left]);
left++;
}
}
while ( !myStack.empty() && right < len) {
if ( myStack.top() == vOut[right] ) {
right++;
myStack.pop();
} else {
break;
}
}
if (myStack.empty()) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
2. 简单的动态规划，注意前面几个元素的确定
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int time;
int len;
int temp;
int left, right;
vector<int> vIn;
int dp[50001] = {0};
cin >> len;
for (int oo = 0; oo < len; oo++) {
cin >> temp;
vIn.push_back(temp);
}
dp[1] = vIn[0];
if (len >= 2 ) {
dp[2] = max(vIn[0], vIn[1]);
if (len >= 3 ) {
dp[3] = max(dp[2], vIn[2]);
}
}
for (int i = 4; i <= len; i++) {
dp[i] = max(max(dp[i - 2], dp[i - 1] ), vIn[i - 1] + dp[i - 3] );
}
cout << dp[len] << endl;
return 0;
}
3. 双指针模拟过程
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int time;
int number;
int temp;
int left = -1;
int ask;
int weight = 0;
int answer = 0;
vector<int> coco;
vector<int> bags;
cin >> number;
cin >> ask;
for (int oo = 0; oo < number; oo++) {
cin >> temp;
coco.push_back(temp * temp);
}
for (int oo = 0; oo < ask; oo++) {
cin >> temp;
bags.push_back(temp);
}
for (int i = 0; i < ask; i++) {
while (left < number - 1 && weight + coco[left + 1] <= bags[i] ) {
answer++;
weight += coco[left + 1];
left++;
}
cout << answer << " ";
}
return 0;
}
4. map实现即可
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <stack>
using namespace std;
int main() {
vector<int> coco;
vector<int> bags;
string temp;
string s;
cin >> s;
int askTimes;
map<string, string> m1;
string tempKey;
string tempValue;
int left = 0, right = 0;
while (right < s.size()) {
if (s[right] == '=') {
tempKey = s.substr(left, right - left);
right++;
left = right;
} else if ( s[right] == ';' ) {
tempValue = s.substr(left, right - left);
right++;
left = right;
m1[tempKey] = tempValue;
} else {
right++;
}
}
cin >> askTimes;
string askString;
for (int i = 0; i < askTimes; i++) {
cin >> askString;
if (m1.count( askString)) {
cout << m1[askString] << endl;
} else {
cout << "EMPTY" << endl;
}
}
return 0;
}
5. 二维dp。dp[i][j]表示第i天，还有j次特殊机会时的最大收益。注意没有使用特殊功能时, dp[i][0]要赋好初始值。
