美团点评 2019校招 后台开发方向职位试卷
第一部分选择考IQ；第二部分选择30道很繁杂，主要是java，数据库；编程题第一题是遍历无向图的最短路径，忘记截一下题目了；不过截了第二道。(第一题参考https://www.nowcoder.com/discuss/104554?type=0&order=0&pos=7&page=1的思路；侵删,仅供参考);
第一题:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int e[N];
int main(){
int n;
while (cin >> n){
memset(e, 0, sizeof(e));
for (int i = 0; i<n - 1; i++){
int a, b;
cin >> a >> b;
e[b] = e[a] + 1;
}
int depth = 0;
for (int i = 1; i <= n; i++)
depth = e[i]>depth ? e[i] : depth;
cout << 2 * n - 2 - depth << endl;
}
return 0;
}
第二题：
#include <bits/stdc++.h> using namespace std; int main(){ int n,k,t; while(cin>>n>>k>>t) { if (n == 0) cout << 0 << endl; vector<int> v0; int cnt = 0; while (n--) { int num; cin >> num; v0.push_back(num); } map<int, int> dynamic;//维持一个动态表 for (int i = 0; i < k; i++) dynamic[v0[i]]++; for (auto j : dynamic) { if (j.second >= t) { cnt++; break; } } //动态表变化的同时查找是否有满足题意的区间 for (int i = k; i < v0.size(); i++) { dynamic[v0[i - k]]--; dynamic[v0[i]]++; for (auto j : dynamic) { if (j.second >= t) { cnt++; break; } } } cout << cnt << endl; } return 0; }
#美团##校招##笔试题目##题解##Java工程师#
