325美团后端笔试

感觉很多题和leetcode相似

1.火车

#include <bits/stdc++.h>
//int t;
using namespace std;
	
int t;
int a[50001];
int b[50001];
int n;
stack<int>st;
int main()
{
	scanf("%d",&t);
	while(t --){
		while(!st.empty())st.pop();
		scanf("%d",&n);
		for(int i = 0; i < n; i++){
			scanf("%d",&a[i]);
		}
		for(int i = 0; i < n; i++){
			scanf("%d",&b[i]);
		}
		int i = 0;
		int j = 0;
		while(i < n && j < n){
			st.push(a[i]);
			i++;
			while(!st.empty() && b[j] == st.top()){
				st.pop(); 
				j++;
			}
		}
	//	printf("i = %d j = %d\n",i,j);
		if(i == n && j == n){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	}
	return 0;
}

2.选糖果 类似于打家劫舍？

#include <bits/stdc++.h>

using namespace std;
vector<int>a;
int n;
int dp[50001][2];
int main()
{
	cin>>n;
	int t;
	for(int i = 0; i < n; i++){
		cin>>t;
		a.push_back(t);
	}
	dp[0][0] = 0;
	dp[0][1] = a[0];
	for(int i = 1; i < n; i++){
		if(i == 1){
			dp[i][1] = a[1];
			dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
		}
		else{
			dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
			dp[i][1] = dp[i-2][0] + a[i]; 
		}
	} 
	cout << max(dp[n-1][1],dp[n-1][0]);
	return 0;
}

3.书包选方块

老是18% 最后排序+特判过了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll m;
ll a[50001];
vector<ll>dp;
int main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		scanf("%lld",&a[i]);
	}
	sort(a,a+n);
	for(int i = 0; i < n; i++){
		a[i] = a[i] * a[i];
	}
	dp.resize(n);
	dp[0] = a[0];
	for(int i = 1; i < n; i++){
		dp[i] = dp[i-1] + a[i];
	}
	ll temp = 0;
	for(int i = 0; i < m; i++){
		scanf("%lld",&temp);
		auto t = lower_bound(dp.begin(),dp.end(),temp);
		int pos = t - dp.begin();
	//	std::cout << dp[pos] << " ";
		while(pos >= 0 && dp[pos] >temp)pos--;
	//	printf("%lld\n",pos+1);
	    if(temp >= dp[n-1])printf("%d ",n);
		else printf("%lld ",pos+1);
	}
	return 0;
}

4.字符串哈希

#include <bits/stdc++.h>
using namespace std;
string s;
string temp1;
string temp2;
int f = 0;
int n;
unordered_map<string,string>mp;
int main()
{
	cin >> s;
	for(char c:s){
		if(c == '='){
			f = 1;
		} 
		else if(c == ';'){
			mp[temp1] = temp2;
			f = 0;
			temp1 = "";
			temp2 = "";	
		}
		else{
			if(!f)temp1 += c;
			else temp2 += c;
		}
	}	 
	cin >> n;
	string t;
	while(n -- ){
		cin >> t;
		if(mp.find(t) != mp.end()){
			cout << mp[t] << endl;
		}
		else cout << "EMPTY" << endl; 
	}
	return 0;
}

5.选糖果2 还是动态规划

#include <bits/stdc++.h>
using namespace std;

int n,k;

int dp[2001][1001][2];

int a[2001];

int main()
{
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
memset(dp,0,sizeof(dp));
//	for(int i = k; i >= 0; i--){
//		for(int j = 0; j < n; j++){
//		dp[j][i][0] = 0;
//		dp[j][i][0] = 0;
//		}}
	dp[0][0][1] = a[0];
	for(int i = k; i >=0 ;i--)dp[0][k][1] = a[0];
	for(int i = k; i >= 0; i--){
		for(int j = 1; j < n; j++){
			dp[j][i][0] = max(dp[j-1][i][1],dp[j-1][i][0]) ;
			dp[j][i][1] = max(dp[j-1][i][0],dp[j-1][i+1][1]) + a[j];
			//cout << dp[j][i][0] << " " << dp[j][i][1] << endl;
			
			
		}
	}
	printf("%d",max(dp[n-1][0][1],dp[n-1][0][0]));
	return 0;
}