讨论/技术交流/面试题目|网易互娱暑期实习算法岗4.18笔试/
面试题目|网易互娱暑期实习算法岗4.18笔试

投的网易游戏(互娱)暑期实习算法岗。笔试一共3道题,考试时间150分钟,我只有第二道题AC了,其他两道凉凉,于是参考大佬的代码(链接会被屏蔽,贴评论里了),自己复盘做了一遍,代码注释仅供参考。过了几天题目可能有些记不清了,如有错误,请在评论区指出,谢谢!

欢迎大家多多补充思路!

第一题:
A和B队打乒乓球赛,每队有3名男性和3名女性,安排两队进行男双、女双和男女混合双打共3场比赛。已知A和B队每名队员的战力值,规定在每场比赛中,若A队队员战力值总和大于等于B队,则A队获胜;若B队队员战力值总和大于A队,则B队获胜。若某队赢的场次大于等于2次,则该队赢得比赛。为了使B队赢得乒乓球赛,请你计算队员安排有多少种?

输入:第一行T表示共有T组数据,第二行和第三行为第一组数据,分别表示A队6名队员战力值,前三个为男性,后三个为女性。第三行表示B队6名队员战力值。以此类推。
输出:使B队获胜的队员比赛安排方法共几种。

示例:
输入:
2
100 50 40 100 50 40
50 45 40 50 45 40
2 2 2 2 2 2
1 1 1 1 1 1
输出:
1
0
解释:男双比赛中,安排A队战力值为50和40的男性,安排B队战力值为50和45的男性,B队战力值之和为95,大于A队战力值之和90,B队获胜;女双比赛中,安排A队战力值为50和40的女性,安排B队战力值为50和45的女性,B队获胜;男女混双比赛中,安排A队战力值为100的男性和100的女性,安排B队战力值为40的男性和40的女性,A队获胜。第一组数据只有这1种安排方式能够使B队赢得比赛。

解题思路:每队有9种人员参赛安排方法,暴力解法。

代码:

#include<iostream>
#include<vector>
using namespace std;

int arr[9][3][2] = {//{{男双},{男女},{女双}} 每队有9种安排
	{{0,1}, {2, 3}, {4, 5}},
	{{0,1}, {2, 4}, {3, 5}},
	{{0,1}, {2, 5}, {3, 4}},
	{{0,2}, {1, 3}, {4, 5}},
	{{0,2}, {1, 4}, {3, 5}},
	{{0,2}, {1, 5}, {3, 4}},
	{{1,2}, {0, 3}, {4, 5}},
	{{1,2}, {0, 4}, {3, 5}},
	{{1,2}, {0, 5}, {3, 4}},
};

int main() {
	int T = 0;
	cin >> T;
	int n = 6;
	for (int i = 0; i < T; i++) {//读入一组数据
		vector<int> A(n, 0);// 男*3 女*3
		vector<int> B(n, 0);
		for (int j = 0; j < n; j++) {
			cin >> A[j];
		}
		for (int j = 0; j < n; j++) {
			cin >> B[j];
		}
		int ans = 0;
		for (int i = 0; i < 9; i++) {//A队安排方式
			for (int j = 0; j < 9; j++) {//B队安排方式
				int win = 0;
				for (int k = 0; k < 3; k++) {//3场比赛
					int team_a = 0;
					int team_b = 0;
					team_a = A[arr[i][k][0]] + A[arr[i][k][1]];
					team_b = B[arr[j][k][0]] + B[arr[j][k][1]];
					if (team_b > team_a) win++;   
				}
				if (win >= 2) ans++;    //B队赢
			}
		}
		cout << ans << endl;
	}
	return 0;
}

第二题:
N个小朋友围成一圈,按顺时针顺序猜拳,可以从任意一个小朋友开始猜拳,共猜拳M次。当前小朋友和下一个小朋友按以下规则猜拳:
(1)若当前小朋友猜拳获胜,则下一个小朋友淘汰出局,当前小朋友进入下一次猜拳;
(2)若下一个小朋友猜拳获胜,则当前小朋友淘汰出局,下一个小朋友进入下一次猜拳;
(3)若猜拳平局,无人淘汰出局,下一个小朋友成为下一次猜拳的当前小朋友,进入下一次猜拳。
假设每个小朋友的出拳方式固定,请问M次猜拳结束后,圈中最多剩下几个小朋友?
规定出拳方式:石头——‘R’,剪刀——‘S’,布——‘C’。石头-剪刀,石头获胜;石头-布,布获胜;剪刀-布,剪刀获胜。

输入:第一行T表示有T组数据,第二行和第三行为一组数据:第二行N和M,表示N个小朋友猜拳M次,第三行表示每个小朋友的出拳。以此类推。
输出:M次猜拳后圈中最多剩下几个小朋友。

示例:
输入:
2
5 6
RRRRR
4 3
RSCR
输出:
5
2

解题思路:注意题目中可以从任意小朋友开始猜拳。

代码:

#include<iostream>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

int main() {
	int T = 0;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int ans = 0;
		int N = 0;
		int M = 0;
		cin >> N >> M;
		string str;
		cin >> str;
		int k = 0;
		if (M == 0) {
			ans = N;
		}
		else {
			for (int start = 0; start < N; start++) {
				k = start;		//从任意起点开始
				int sub_ans = 0;
				int n = N;
				string str_c = str;
				for (int j = 0; j < M; j++) {//猜拳M次
					if (n == 1) {
						break;
					}
					if (k + 1 < n) {//圆圈未循环
						//当前小朋友赢
						if ((str_c[k] == 'R' && str_c[k + 1] == 'S') ||
							(str_c[k] == 'S' && str_c[k + 1] == 'C') ||
							(str_c[k] == 'C' && str_c[k + 1] == 'R')) {
							n--;	//总人数减1
							str_c.erase(str_c.begin() + k + 1);    
						}
						//下一个小朋友赢
						else if ((str_c[k] == 'R' && str_c[k + 1] == 'C') ||
							(str_c[k] == 'S' && str_c[k + 1] == 'R') ||
							(str_c[k] == 'C' && str_c[k + 1] == 'S')) {
							n--;
							str_c.erase(str_c.begin() + k);
						}
						//平局
						else {
							k++;
						}
					}
					else {//圆圈循环
						//当前小朋友赢
						if ((str_c[k] == 'R' && str_c[0] == 'S') ||
							(str_c[k] == 'S' && str_c[0] == 'C') ||
							(str_c[k] == 'C' && str_c[0] == 'R')) {
							n--;
							str_c.erase(str_c.begin() + 0);
							k--;
						}
						//下一个小朋友赢
						else if ((str_c[k] == 'R' && str_c[0] == 'C') ||
							(str_c[k] == 'S' && str_c[0] == 'R') ||
							(str_c[k] == 'C' && str_c[0] == 'S')) {
							n--;
							str_c.erase(str_c.begin() + k);
							k = 0;
						}
						//平局
						else {
							k = 0;
						}
					}
				}
				sub_ans = n;
				ans = max(ans, sub_ans);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

第三题:
在一款闯关游戏中,闯关记录中记录闯关成功玩家的id和分值。排行榜记录玩家的闯关分数排行。每次有玩家闯关成功时,若该玩家分值为排行榜的中位数,则发送一份礼物。每名玩家只能获得一份礼物。输入闯关记录,问共发送几份礼物?
输入:第一行T表示共有T组数据,第二行N表示有N条闯关记录,之后N行表示玩家id和分值。
输出:礼物发送数量。

示例:
输入:
1
5
4 2
3 3
2 2
1 1
1 2
输出:
3

解题思路:注意排行榜中每名玩家只能有一条记录。

代码:

#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;

void Insert(vector<int>& rank, int score) {
	//rank中按从小到大顺序记录分值
	vector<int>::iterator it = rank.begin();
	if (rank.size() == 0) {//第一条记录
		rank.push_back(score);
		return;
	}
	if (score <= rank[0]) {//当前分值小于记录最小值
		rank.insert(it, score);
	}
	for (it = rank.begin(); (it + 1) != rank.end() && (it) != rank.end(); it++) {//当前分值在记录中间
		if (*(it) <= score && *(it + 1) >= score) {
			rank.insert(it + 1, score);
			return;
		}
	}
	rank.insert(it + 1, score);
}

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {//每一组数据
		int N;
		cin >> N;

		vector<int> rank;	//分数排行
		set<int> gift;		//礼物发送记录
		map<int, int> id_score;		//玩家闯关记录
		int id, score;
		for (int j = 0; j < N; j++) {//N个闯关记录
			cin >> id >> score;
			map<int, int>::iterator map_it = id_score.find(id);    
			if (map_it != id_score.end() && map_it->second >= score) {//若老玩家未打破旧闯关记录
				continue;		//不更新记录
			}
			if (map_it != id_score.end()) {//若老玩家有新闯关记录
				for (vector<int>::iterator it = rank.begin(); it != rank.end(); it++) {
					if (*(it) == map_it->second) {//在rank中,有相同的分数,即之前的玩家可能已经发送过礼物
						rank.erase(it);		//删除旧记录
						break;
					}
				}
			}
			Insert(rank, score);
			int n_rank = rank.size();
			if (n_rank % 2 == 1) {//奇数个记录
				if (score == rank[n_rank / 2]) {//发放礼物
					gift.insert(id);
				}
			}
			else {//偶数个记录
				if ((rank[n_rank / 2] + rank[n_rank / 2 - 1]) % 2 == 0 &&      //若中位数为整数 && 中位数==score(注意:条件一必须有)
					(rank[n_rank / 2] + rank[n_rank / 2 - 1]) / 2 == score) {
					gift.insert(id);
				}
			}
			id_score[id] = score;        //闯关记录
		}
		cout << gift.size() << endl;
	}
	return 0;
}
2

向大佬学习!

展开全部 5 讨论