美团测开秋招笔试

总共20道选择题+3道代码题(ak) , 希望有面试!!!

20道选择题

数据库
数据结构
散列表，求平均查找长度
共享内存和消息传递对比
.....

1.染色

// n个无色的点
// 每次两个操作之一 : 
// 1 . 选一个染成红色
// 2 . 选[l,r],红>无，全变红
// 求n个点全染红的最少次数

模拟就ok :

#include<bits/stdc++.h>
using namespace std ;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl '\n'

// n个无色的点
// 每次两个操作之一 : 
// 1 . 选一个染成红色
// 2 . 选[l,r],红>无，全变红
// 求n个点全染红的最少次数 

// 至少多少次操作  
// 第1次 : 1
// 2 : 2
// 3 : 3
// 4 : 3+2=5
// 5 : 5+4=9
// 6 : 9+8=17 

// a[i] = 2*a[i-1]-1 ;

const int N = 1e5+10 ;
int a[N] ;
int ld = -1 ;

inline void init(){
	a[1] = 1 ;
	a[2] = 2 ;
	a[3] = 3 ;
	a[4] = 5 ;
	int ma = 1e9 ;
	for(int i=5;;i++){
		a[i] = 2*a[i-1]-1;
		if(a[i]>ma) {
			ld = i;
			break ;
		}
	}
}

inline void YSS(){
	int n ; cin >> n ;
	// ld = 32 , 直接暴力
	int ans = -1 ;
	for(int i=1;i<=n;i++){
		if(a[i]>=n){
			ans = i ;
			break ;
		}
	} 
	cout << ans << endl ;
}

signed main(){
	IOS 
	int _ ;
	cin >> _ ;
	init() ;
	while(_--){
		YSS() ;
	} 
	return 0 ;
}

2.判断字符串合法

// 判断字符串是否合法 
// 三个部分要求不同

模拟即可 :

#include<bits/stdc++.h>
using namespace std ;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl '\n'

int len = 15 ;

// 判断字符串是否合法 

string B = "invalid" , A = "valid" ;

bool pd(int y){
	return (y%4==0&&y%100!=0) || (y%400==0) ;
}

bool pd1(int x){
	if(x==1||x==3||x==5||x==7||x==8||x==10||x==12) return true ;
	else return false ;
}

int f(string s){
	int x = 0 ;
	for(char c : s){
		x = x * 10 + (c-'0') ;
	}
	return x ;
}

inline void YSS(){
	string s ; cin >> s ;
	bool tag = true ;
	int n = s.size() ;
	if(n!=len) {cout << B << endl ; return ;}
	for(int i=0;i<3;i++){
		if(!(s[i]>='A'&&s[i]<='Z')) {cout << B << endl ; return ;}
	}
	for(int i=3;i<n;i++){
		if(!(s[i]>='0'&&s[i]<='9')) {cout << B << endl ; return ;}
	}
	s = s.substr(3,8) ;
	string a = s.substr(0,4) , b = s.substr(4,2),c=s.substr(6,2) ;
	int year = f(a) , mon = f(b) , day = f(c) ;
	if(pd(year)){
		if(mon<1||mon>12){
			tag = false;	
		}else if(mon==2){
			if(day<1||day>29) tag = false ;
		}else if(pd1(mon)){
			if(day<1||day>31) tag = false ;
		}else{
			if(day<1||day>30) tag = false ;
		}
	}else{
		if(mon<1||mon>12){
			tag = false ;
		}else if(mon==2){
			if(day<1||day>28) tag = false ;
		}else if(pd1(mon)){
			if(day<1||day>31) tag = false ;
		}else{
			if(day<1||day>30) tag = false ;
		}
	}
	if(tag) {cout << A << endl ; return ;}
	else {cout << B << endl ; return ;}
}

signed main(){
	IOS 
	int _ ;
	cin >> _ ;
	while(_--){
		YSS() ;
	} 
	return 0 ;
}

3.最大美观值

// m种不同的标签(每种只有一个)
// 第i种物品，如果贴上ai标签，那么美观值为bi,不贴ai美观值为ci ;

// 求所有物品最大美观值

用哈希表记录，取增加最大的即可 ;

#include<bits/stdc++.h>
using namespace std ;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl '\n'
#define pb push_back

// m种不同的标签(每种只有一个)
// 第i种物品，如果贴上ai标签，那么美观值为bi,不贴ai美观值为ci ;

// 求所有物品最大美观值 

inline void YSS(){
	int n , m ; cin >> n >> m ;
	vector<int> a(n+1),b(n+1),c(n+1) ;
	unordered_map<int,vector<int>> mp ;
	for(int i=1;i<=n;i++) cin >> a[i] ;
	for(int i=1;i<=n;i++) cin >> b[i] ;
	for(int i=1;i<=n;i++) cin >> c[i] ;
	int ans = 0 ;
	for(int i=1;i<=n;i++){
		ans += c[i] ;
		if(c[i]<b[i]){
			mp[a[i]].pb(b[i]-c[i]) ;	
		}
	}
	// 对于每一个mp[i],选择一个最大提升即可 
	for(auto& it : mp){
		auto& vc = it.second ;
		sort(vc.begin(),vc.end());
		ans += vc.back() ;
	}
	cout << ans << endl ;
}

signed main(){
	IOS 
	int _ = 1;
	// cin >> _ ;
	while(_--){
		YSS() ;
	} 
	return 0 ;
}

#你都收到了哪些公司的感谢信？##软件开发#

秋招joker 文章被收录于专栏

记录秋招...