美团2022年机试

评价

总体而言，比其他公司的难度低，选择题只有3题，都是机器学习，而且有一题，关于半监督就是从课本上拿下来的。

编程题的4道总体难度不高，最后一题查找不知道怎么办，AC了72%，其他都通过了。

编程题

题目1

n个数，找出[k-1,k+1]范围内数字数量最多的区间内包含的数字个数。

输入n，第二行输入n个数，每个数范围是1-100。

示例

6
1 2 2 3 5 5
输出

4

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main(){
	int n;
	cin >> n;
	//vector<int> arr;
	map<int, int> counts;
int minVal = 100, maxVal = 0;
	for(int i = 0; i < n; i++){
		int value;
		cin >> value;
		counts[value]++;
		if(value > maxVal) maxVal = value;
		if(value < minVal) minVal = value;
	}
	int res = 0;// minVal = arr[0], maxVal = arr[n - 1]
	for(int cur = minVal; cur < maxVal; cur++){
		int tempcount = counts[cur-1] + counts[cur] + counts[cur+1];
		res = max(tempcount, res);
	}
	cout << res;
} 

题目2

从（0，0）到（n,m)，尽量走'o'的路，只能向下和向右移动，计算最少需要经过几个'x'。本质是《剑指offer》13相似。

示例

5 5
oxxxx
xxoox
oooxo
xxxxo
ooooo
输出

2

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int main(){
	int m,n;
	cin >> n >> m;
	vector<vector<int>> weight(n, vector<int>(m, 0));
	char c;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m;j++){
			cin >> c;
			if(c == 'x') weight[i][j] = 1; 
		}
	}
	vector<vector<int>> sum(n, vector<int>(m, 50000));
	sum[0][0] = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m;j++){
			if(i > 0) sum[i][j] = min(sum[i][j], sum[i-1][j] + weight[i-1][j]);
			if(j > 0) sum[i][j] = min(sum[i][j], sum[i][j-1] + weight[i][j-1]);
		}
	}
	cout << sum[n-1][m-1]; 

}

题目3

本质是替换字母使连续字符长度最大leetcode 424，相似的题目在其他公司也有出现。

示例

10 2

--++--+++-
输出

7

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int main(){
	int n,k;
	cin >> n >> k;
	string str;
	cin >> str;
	int i = 0, ans = 0;
	while(i <= n-k){
		int x = k, j = i + 1;
		while(j < n){
			if(str[i] != str[j]){
				if(x == 0) break;
				x--;
			}
			j++;
		}
		ans = min(n, max(ans, j-i+x));
		i++;
		while(i<n && str[i-1]==str[i]) i++;
	}
	cout << ans;
}

题目4

第一行两个正整数n和q，n表示奶茶的品牌数量，q表示操作数量。第二行n个空格隔开的正整数，表示每个奶茶品牌的单价利润。接下来q个操作，每个操作为下列的一种：Add x y ：品牌x的奶茶增加销量y。Query BestSales ：查询当前操作为止销量最多的奶茶品牌，若不唯一输出编号最小的。Query BestProfit ：查询当前操作为止利润最多的奶茶品牌，若不唯一输出编号最小的。1 <= n <= 100000, 1 <= q <= 500保证品牌x的范围在[1, n]之内，保证销量y增加值在[1, 100]之内销量和利润的答案保证在 [1, 1e9] 的范围内

示例

2 6
1 2
Add 1 3
Add 2 2
Query BestSales
Query BestProfit
Add 1 1
Query BestProfit
输出

1

2

1

代码

AC 72%

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int main(){
	int n, q;
	cin >> n >> q;
	vector<int> profit(n);
	for(int i = 0;i < n;i++)
		cin >> profit[i];//输出品牌号需要加1
	vector<int> totalSale(n), totalPro(n);
	for(int i = 0; i < q; i++){
		string query;
		cin >> query;
		if(query[0] == 'A'){
			int brand, num;
			cin >> brand >> num;//需要-1 
			totalSale[brand - 1] += num;
			totalPro[brand-1] += num * profit[brand-1];
		}
		else{
			cin >> query;
			if(query=="BestSales"){
				int resSale = 0, resbrand = -1;
				for(int i = 0;i <n;i++){
					if(resSale< totalSale[i]){
						resSale = totalSale[i];
						resbrand = i;
					}
					
				}
				cout<<resbrand + 1 << '\n';
			}
			else{
				int resPro = 0, resbrand = -1;
				for(int i = 0;i <n;i++){
					if(resPro< totalPro[i]){
						resPro = totalPro[i];
						resbrand = i;
					}
					
				}
				cout<<resbrand + 1 << '\n';
			}
		}
	} 
	return 0;
}