美团笔试
1. 字符串修改
输入： 一个字符串S
任意一个字符串，修改字符，如何才能使得修改后的字符串不包含两个连续相同的字符？模拟即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
int T;
int main(int argc, char * argv[]){
string s;
cin >> s;
int n = s.size();
int ans = 0;
// 判断当前字符和上一字符是否相等，如果不相等，可以暂时修改为"+"
for(int i = 1; i < n; i++){
if(s[i] == s[i-1]){
s[i] = '+';
ans++;
}
}
cout << ans;
return 0;
}
2. 最优规划
输入：
- 第一行 n， m， k 分别代表行数、列数和颜色转换需要的金币数
- 输入 colors颜色二维数组
- 输入金币二维数组代表每点的金币个数
动态规划即可，
dp[i][j]代表到达 (i,j) 最大的价值，转移方程也就不难推出了。
需要注意的是
- 上一步
(i-1,j) or (i, j-1)是否可以到达（如果为-1那么就是不可达） - 如果上一步到此步有颜色转换，那么上一步是否可以移动到此位置也就是
dp[i-1][j] or dp[i][j-1] >= k
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
int T, n, m, k;
const int MAXN = 200;
int coins[MAXN][MAXN];
char colors[MAXN][MAXN];
int main(int argc, char * argv[]){
cin >> n >> m >> k;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> colors[i][j];
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> coins[i][j];
int dp[MAXN][MAXN];
memset(dp, 0, sizeof(dp));
int ans = 0;
dp[0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i or j) dp[i][j] = -1;
else continue;
// 需要注意 1. 上一步是否可以到达（如果为-1那么就是不可达） 2.如果有颜色转换，上一步是否可以移动到此位置也就是是否大于等于K
if(i > 0 and dp[i-1][j] >= 0){
if(colors[i-1][j] == colors[i][j]) dp[i][j] = max(dp[i][j], dp[i-1][j] + coins[i][j]);
else if(dp[i-1][j] >= k) dp[i][j] = max(dp[i][j], dp[i-1][j] + coins[i][j] - k);
}
// dp[i][j] = -1;
if(j > 0 and dp[i][j-1] >= 0){
if(colors[i][j-1] == colors[i][j]) dp[i][j] = max(dp[i][j], dp[i][j-1] + coins[i][j]);
else if(dp[i][j-1] >= k) dp[i][j] = max(dp[i][j], dp[i][j-1] + coins[i][j] - k);
}
ans = max(ans, dp[i][j]);
}
}
cout << ans;
return 0;
}
3. 区间覆盖最大次数
输入 ：
第一行： n 代表区间个数
第二行， 输入所有区间的起始端点
第三行， 输入所有区间的末尾端点
使用差分数组, 插入[from, to]区间的时候，使得mp[from]++, mp[to+1]--, 然后再通过前缀求和，就可以得到每个点的覆盖次数。需要注意的是 1^9+10的数据情况下，我们不能模拟全部点，应该只保存端点，因此应该使用散列表。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
int T;
const int MAXN = 1e5 + 10;
int from[MAXN], to[MAXN], n;
int main(int argc, char * argv[]){
map<int, int> mp;
cin >> n;
for(int i = 0; i < n; i++) cin >> from[i];
for(int i = 0; i < n; i++) cin >> to[i];
for(int i = 0; i < n; i++){
mp[from[i]]++;
mp[to[i] + 1]--;
}
int max_count = 0;
int count = 0;
vector<pair<int,int>> p;
for(auto it : mp){
count += it.second;
max_count = max(count, max_count);
p.push_back({it.first, count});
}
int ans = 0;
//如果从某一端点开始可以取得最大值，那么此段点到下一端点范围的点都满足题意
for(int i = 0; i < p.size(); i++){
if(p[i].second == max_count){
ans += p[i+1].first - p[i].first;
}
}
cout << max_count << " " << ans;
return 0;
}
4. 坦克大战
大模拟即可，题目挺复杂的，也忘记截图保存学习了，此题只过了82%。
感谢@hammer 提供的题目简要概括：
@hammer : 坦克大战题目应该是出自知乎，除了子弹速度不一样 https://zhuanlan.zhihu.com/p/575687028
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
int T;
int flag[16][16]; //0 未被占领 1 2 分别占领
unordered_map<char,int> xx;
unordered_map<char,int> yy;
unordered_map<char, int> hh;
string s, t;
bool checkMove(char ch){
return ch == 'U' or ch == 'D' or ch == 'L' or ch == 'R';
}
int main(int argc, char * argv[]){
cin >> s >> t;
xx['U'] = -1, xx['D'] = 1, xx['L'] = xx['R'] = 0;
yy['L'] = -1, yy['R'] = 1, yy['D'] = yy['U'] = 0;
int n = s.size();
//代表位置
int x1 = 0, y1 = 0, x2 = 15, y2 = 15;
//代表朝向
int h1 = 'R', h2 = 'L';
// a ： 代表经过几轮结束游戏 b: 结局情况
// b= 0：未定； 1：D胜, 2: W胜， 3：平局
int a = n - 1, b = 0;
flag[0][0] = 1, flag[15][15] = 2;
for(int i = 0; i < 256; i++){
int cx1 = x1, cy1 = y1, cx2 = x2, cy2 = y2;
//判断是否能否被摧毁
bool at1 = false, at2 = false;
if(not checkMove(s[i])){
if(h1 == 'U' and y1 == y2 and x2 < x1){ a = i, b = 1; at1 = true;}
if(h1 == 'R' and x1 == x2 and y2 > y1){ a = i, b = 1; at1 = true;}
if(h1 == 'D' and y1 == y2 and x2 > x1){ a = i, b = 1; at1 = true;}
if(h1 == 'L' and x1 == x2 and y2 < y1){ a = i, b = 1; at1 = true;}
}
if(not checkMove(t[i])){
if(h2 == 'U' and y1 == y2 and x2 > x1){ a = i, b = 2; at2 = true;}
if(h2 == 'R' and x1 == x2 and y2 < y1){ a = i, b = 2; at2 = true;}
if(h2 == 'D' and y1 == y2 and x2 < x1){ a = i, b = 2; at2 = true;}
if(h2 == 'L' and x1 == x2 and y2 > y1){ a = i, b = 2; at2 = true;}
}
//如果可以相互摧毁，那么平局
if(at1 or at2){
if(at1 and at2) a = i, b = 3;
break;
}
cx1 = x1 + xx[s[i]], cy1 = y1 + yy[s[i]];
cx2 = x2 + xx[t[i]], cy2 = y2 + yy[t[i]];
//相撞，平局
if(cx1 == cx2 and cy1 == cy2 and flag[cx1][cy1] == 0){
a = i;
b = 3;
break;
}
//尝试改变位置
if(checkMove(s[i])){
h1 = s[i];
if(flag[cx1][cy1] != 2) flag[cx1][cy1] = 1, x1 = cx1, y1 = cy1;
}
if(checkMove(t[i])){
h2 = t[i];
if(flag[cx2][cy2] != 1) flag[cx2][cy2] = 2, x2 = cx2, y2 = cy2;
}
}
//前面未定胜负，查看占领区域数量
if(b == 0){
int cnt1 = 0, cnt2 = 0;
for(int i = 0; i < 16; i++){
for(int j = 0; j < 16; j++){
if(flag[i][j] == 1) cnt1++;
if(flag[i][j] == 2) cnt2++;
}
}
if(cnt1 > cnt2) b = 1;
else if(cnt1 < cnt2) b = 2;
else b = 3;
a = n - 1;
}
if(b == 1) cout << a + 1 << endl << "D" << endl;
else if(b == 2) cout << a + 1 << endl << "W" << endl;
else cout << a + 1 << endl << "P" <<endl;
return 0;
}
5. 平衡节点个数
给你一个数组，然后里面存储的每个节点的父节点编号，以及每个节点的颜色（R或者B），问这棵树中所有平衡节点的个数？平衡节点的意思是指：该节点和该节点的所有子树的两种颜色的节点个数相同。
首先根据题意构造出原来多叉树，然后递归求解每个节点左右子树的颜色总数平衡即可，力扣有大量这种题目。
注意，由于一直在调第四题，所以这道题没有a完就提交了，也没看过了多少样例，听同学说是多叉树，么看清题意。但是思路应该都差不多，所以该题代码仅供参考叭~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;
struct Node{
int val;
int color;
Node *left;
Node *right;
Node(int _color){
this->color = _color;
left = nullptr;
right = nullptr;
}
};
int T;
// unordered_map<Node*, pair<int,int>> mp;
const int MAXN = 100001;
unordered_map<int, Node*> mp;
int ans = 0;
pair<int,int> cal(Node* node){
if(not node) return {0, 0};
auto leftHave = cal(node->left);
auto righthave = cal(node->right);
int R = leftHave.first + righthave.first + (node->color == 0);
int L = leftHave.second + righthave.second + (node->color == 1);
cout << R << L << endl;
if(R == L) ans++;
return make_pair(R, L);
}
void print(Node* root){
if(not root) return;
print(root->left);
cout << root->color;
print(root->right);
}
int main(int argc, char * argv[]){
int n;
cin >> n;
string color;
cin >> color;
vector<Node*> s(n + 1);
for(int i = 1; i <= n; i++){
int c = color[i-1] == 'R' ? 0 : 1;
s[i] = new Node(c);
}
int father;
for(int i = 2; i <= n; i++) {
cin >> father;
if(not s[father]->left) s[father]->left = s[i];
else s[father]->right = s[i];
}
ans = 0;
cal(s[1]);
cout << ans;
return 0;
}
如有纰漏，还请评论指正 欢迎关注此小站 https://tans.fun ~ 如果有问题，可以评论，
建议注明正确的邮箱，这样可以邮箱给您回复
注：该贴题目以及答案仅供学习参考使用，如有侵权请联系博主删除。
