讨论/求职面试/美团|暑期实习算法岗|上海|2021.4.11|/
美团|暑期实习算法岗|上海|2021.4.11|

第二次做大厂笔试,虽然没有一道题全过了(苦笑)但还是记录一下。
希望各位大佬多多指导!

问题1:
有n座房子整齐排列在一条直线上,按顺序每个房子编号为i(从1开始编号),房子之间的间隔距离相等。A可能住在这n座房子中的任意一座,B想住得离A尽可能近。B的买房预算为k元,请你帮B找到离A最近且房价不超过k的房屋,输出该房屋的编号。
若某座房子房价为0,说明A可能居住于该房,规定此时B无法购买该房。若存在多种购房可能性,输出房屋编号最小的。
输入两行:第一行为n和k,第二行为n座房子的房价。
输出一行:整数房屋编号。
输入示例:
5 3
4 5 0 3 3
输出:
4

解题思路(仅供参考):先找到A可能居住的房屋编号,在每个A可能居住的房屋附近左右遍历房屋价格,记录离该房最近且房价小于等于k的房屋编号。最后比较所有上述符合要求的房屋与A的距离,选择距离最小的。

考试时通过20%左右测试案例。出错的目前想不出来是为什么QAQ。
代码(仅供参考):

#include<iostream>
#include<vector>

using namespace std;

int main() {
	int n, k;
	//input
	cin >> n >> k;
	vector<int> houseprice(n, 0);

	for (int i = 0; i < n; i++) {
		cin >> houseprice[i];
	}

	//小美居住的房间
	vector<int> xiaomei;
	for (int i = 0; i < n; i++) {
		if (houseprice[i] == 0) {
			xiaomei.push_back(i);
		}
	}
	vector<int> t_house;
	vector<int> min_dis;
	for (int i = 0; i < xiaomei.size(); i++) {
		//向左遍历
		int left = 0;
		for (int j = xiaomei[i] - 1; j >= 0; j--) {
			if (houseprice[j] <= k && houseprice[j] != 0) {
				left = j;
				break;
			}
		}
		//向右遍历
		int right = 0;
		for (int j = xiaomei[i] + 1; j < n; j++) {
			if (houseprice[j] <= k && houseprice[j] != 0) {
				right = j;
				break;
			}
		}
		//每个可能的最近房号与距离
		if (xiaomei[i] - left < right - xiaomei[i]) {
			t_house.push_back(left + 1);
			min_dis.push_back(xiaomei[i] - left);
		}
		else {
			t_house.push_back(right + 1);
			min_dis.push_back(right - xiaomei[i]);
		}
	}
	
	//output
	//找出所有可能里面最近的
	int min_x = 0;
	int min_d = 1000;
	for (int i = 0; i < min_dis.size(); i++) {
		if (min_dis[i] > min_d) {
			min_x = i;
			min_d = min_dis[i];
		}
	}

	cout << t_house[min_x] << endl;

	return 0;
}

问题2:
A队和B队比赛射箭,假设A和B队中每位队员均能射中靶心。每队在射箭前设定该队的射箭距离为d,若某个队员射中靶心的射箭距离小于等于d,该队得1分,若某个队员射中靶心的射箭距离大于d,该队得2分。B队队长已知两队中每位队员的射箭距离,计算B队总分最多比A队总分多几分?
输入三行数据,第一行为A和B队的人数,第二行为A队所有成员的射击距离,第三行为B队所有成员的射击距离。输出B队总分比A队总分多出分数的最大值。
输入示例:
2 3
585 375
936 317 185
输出:2

解题思路(仅供参考):把所有人的分数都记录下来,选择每个人的分数作为得分标准d,计算该次得分B队比A队多几分,记录最大分数差。

考试时通过大概30%左右测试用例,会超时。时间复杂度太高了,后来也没有想出提速的方法。
代码(仅供参考):

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

int main() {
	int n, m;
	cin >> n >> m;

	vector<int> M(n, 0);
	vector<int> T(m, 0);
	vector<int> All(m + n, 0);

	int k = 0;
	for (int i = 0; i < n; i++) {
		cin >> M[i];
		All[k++] = M[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> T[i];
		All[k++] = T[i];
	}

	int M_score = n;
	int max_score = 0;
	for (int i = 0; i < m+n; i++) {
	//for (int i = 0; i < n; i++) {
		int d = All[i];
		int M_score = 0;
		int T_score = 0;
		for (int j = 0; j < n; j++) {//M队总分
			if (M[j] > d) M_score += 2;
			else M_score += 1;
		}
		for (int k = 0; k < m; k++) {//T队总分
			if (T[k] > d) T_score += 2;
			else T_score += 1;
		}
		if (T_score - M_score > max_score) max_score = T_score - M_score;
	}

	cout << max_score << endl;
	return 0;
}

问题3:
一串数字仅由0和1组成,假设有一种消除魔法,能够一次消除相邻的三个数。假设可以使用任意次魔法(包括0次),请问数字0的个数和数字1的个数之差最大为多少?
输入两行数据,第一行为数字串的长度,第二行为数字串。
输入示例:
5
00001
输出:3

解题思路(仅供参考):计算每次消除的字符’0’和字符’1’,根据消除次数进行遍历,每次都进行连续消除。缺点是没有考虑到消除的位置可以是不相邻的。

考试时通过20%左右测试案例,这个题我感觉我的思路是不对的,但没想明白应该用什么算法做。
代码(仅供参考):

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

int main() {
	int n = 0;
	cin >> n;

	string arr;
	for (int i = 0; i < n; i++) {
		char input;
		cin >> input;
		arr.push_back(input);
	}

	int max_delete = 0;
	max_delete = arr.size() / 3;

	int max_minus = 0;
	int zero = 0;
	int one = 0;

	//不用魔法
	for (int i = 0; i < n; i++) {
		if (arr[i] == '0') zero++;
	}
	one = n - zero;

	max_minus = abs(zero - one);

	//使用x次魔法
	for (int i = 0; i < max_delete; i++) {
		string deleted;
		int after_zero = 0;
		int after_one = 0;
		for (int j = 0; j <= n - (i+1) * 3; j++) {
			deleted = arr.substr(j, (i+1)*3);
			int deleted_zero = 0;
			int deleted_one = 0;
			for (int k = 0; k < (i+1) * 3; k++) {//计算消除的0的个数
				if(deleted [k] == '0') deleted_zero++;
			}
			deleted_one = (i+1)*3 - deleted_zero;
			after_zero = zero - deleted_zero;
			after_one = one - deleted_one;
			max_minus = max(max_minus, abs(after_zero - after_one));
		}
	}

	cout << max_minus << endl;
	return 0;
}

问题4:
定义关键串:字符串中某个字符的个数严格超过字符串长度的一半称为关键串。定义子串:字符串中的部分连续字符构成子串。
请问一串字符串中有多少个子串为关键串?
输入两行,第一行为字符串长度,第二行为字符串。
输入示例:
5
ccccb
输出:14。其中为关键串的子串为:c, cc, ccc, cccc, ccccb, c, cc, ccc, cccb, c, cc, ccb, c, cb, b。

解题思路:首先得到全部子串,再判断每个子串是否为关键串。
考试时卡在生成全部子串函数上了,想用回溯做但是怎么写都不对(紧张+技巧不熟练),当时胡乱写的函数测试案例通过10%左右。考完试之后写出来了。
代码(仅供参考):

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

vector<string> ans;

void subString(string arr) {
	int n = arr.size();
	for (int cur = 0; cur < n; cur++) {
		string tmp;
		for (int i = cur; i < n; i++) {
			tmp.push_back(arr[i]);
			ans.push_back(tmp);
		}
	}
}

bool isOK(string arr) {
	if (arr.size() == 1) return true;
	int n = arr.size() / 2;
	unordered_map<char, int> hash;
	for (auto x : arr) {
		hash[x]++;
		if (hash[x] > n) return true;
	}
	return false;
}

int main() {
	int n = 0;
	cin >> n;

	string arr;
	for (int i = 0; i < n; i++) {
		char input;
		cin >> input;
		arr.push_back(input);
	}
	//生成全部子串
	subString(arr);
	int num = 0;
	for (int i = 0; i < ans.size(); i++) {
		if (isOK(ans[i])) num++;
	}

	cout << num << endl;

	return 0;
}

感觉自己的技巧还不够熟练,很多问题第一想法都是暴力法。
如果有正确的代码或好的思路请告诉我,我还有很多需要学习的地方!谢谢!
希望大家多多交流,共同进步!
欢迎各位大佬批评指正!

14

请问规定是c++作答吗

展开全部 18 讨论