2023-3-11美团笔试

2023-3-11美团笔试

Tans 8,973 2023-03-09

美团笔试

1. 字符串修改

image-1678599218443

输入: 一个字符串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. 最优规划

image-20230312131423424

输入:

  1. 第一行 n, m, k 分别代表行数、列数和颜色转换需要的金币数
  2. 输入 colors颜色二维数组
  3. 输入金币二维数组代表每点的金币个数

动态规划即可,
dp[i][j]代表到达 (i,j) 最大的价值,转移方程也就不难推出了。
需要注意的是

  1. 上一步(i-1,j) or (i, j-1)是否可以到达(如果为-1那么就是不可达)
  2. 如果上一步到此步有颜色转换,那么上一步是否可以移动到此位置也就是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. 区间覆盖最大次数

image-20230312131443781

输入 :
第一行: 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 ~ 如果有问题,可以评论,
建议注明正确的邮箱,这样可以邮箱给您回复

注:该贴题目以及答案仅供学习参考使用,如有侵权请联系博主删除。

相关阅读

  1. 记录一次美团面试
  2. 2022-4-14携程笔试
  3. 2022-4-24腾讯技术后端场笔试
  4. 2022京东春招笔试4-2
  5. 腾讯音乐笔试2022-4-7场
  6. 2022-4-14携程笔试