美团9月6日后台开发 笔试 编程题
第一题
给定一张包含N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点，那么总路程至少是多少？
输入
第一行包含一个整数N，1≤N≤100000。
接下来N-1行，每行包含两个整数X和Y，表示X号节点和Y号节点之间有一条边，1≤X，Y≤N。
输出
输出总路程的最小值。
思路：走完所有节点类似于深度优先搜索，也就是说除了最后一条路径外，别的路径都经历了正着走，再返回
的过程，也就是两遍，设最后一条路径为x，总分支数为n-1，总路径=2*(n-1-x)+x=2*n-2-x，当x最大时
小明拿到了一个数列a1 , a2 , ... an ，小明想知道存在多少个区间[l,r]同时满足下列两个条件：
1、r-l+1=k;
2、在a l , a l+1,...ar中，存在一个数至少出现了 t 次。
输出满足条件的区间个数。
思路：
先判断n和k的关系，若k>n，直接返回0，若k<n，再进行后续计算
设置一维数组lst[10005]，保存数列中值出现次数
设置count，保存ar-al中出现t次及以上数的个数
设置num,保存区间数
首先从0到n-k-1遍历一遍，对lst、count、num进行初始化
然后将窗口向右滑动，每次从头去一个，从尾部添加一个，动态维护lst、count、num的值
给定一张包含N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点，那么总路程至少是多少？
输入
第一行包含一个整数N，1≤N≤100000。
接下来N-1行，每行包含两个整数X和Y，表示X号节点和Y号节点之间有一条边，1≤X，Y≤N。
输出
输出总路程的最小值。
思路：走完所有节点类似于深度优先搜索，也就是说除了最后一条路径外，别的路径都经历了正着走，再返回
的过程，也就是两遍，设最后一条路径为x，总分支数为n-1，总路径=2*(n-1-x)+x=2*n-2-x，当x最大时
总路径最小，所以转化为求多叉树的深度。
#include<bits/stdc++.h>
using namespace std;
int lst[100005];
int main(){
int n;
while(cin>>n){
memset(lst,0,sizeof(lst));
for(int i = 0;i<n-1;i++){
int a,b;
cin>>a>>b;
lst[b] = lst[a]+1;//当前节点的深度
}
int depth = 0;
for(int i = 1;i<=n;i++)
depth = lst[i]>depth?lst[i]:depth;//找到最大值
cout<<2*n-2-depth<<endl;
}
return 0;
}
第二题using namespace std;
int lst[100005];
int main(){
int n;
while(cin>>n){
memset(lst,0,sizeof(lst));
for(int i = 0;i<n-1;i++){
int a,b;
cin>>a>>b;
lst[b] = lst[a]+1;//当前节点的深度
}
int depth = 0;
for(int i = 1;i<=n;i++)
depth = lst[i]>depth?lst[i]:depth;//找到最大值
cout<<2*n-2-depth<<endl;
}
return 0;
}
小明拿到了一个数列a1 , a2 , ... an ，小明想知道存在多少个区间[l,r]同时满足下列两个条件：
1、r-l+1=k;
2、在a l , a l+1,...ar中，存在一个数至少出现了 t 次。
输出满足条件的区间个数。
思路：
先判断n和k的关系，若k>n，直接返回0，若k<n，再进行后续计算
设置一维数组lst[10005]，保存数列中值出现次数
设置count，保存ar-al中出现t次及以上数的个数
设置num,保存区间数
首先从0到n-k-1遍历一遍，对lst、count、num进行初始化
然后将窗口向右滑动，每次从头去一个，从尾部添加一个，动态维护lst、count、num的值
最后输出num的值即可
#include<bits/stdc++.h>
using namespace std;
int lst[10005];
int main(){
int n,k,t;
while(cin>>n>>k>>t){
if(k<=n){
vector<int> vec;
memset(lst,0,sizeof(lst));
for(int i = 0;i<n;i++){
int x;
cin>>x;
vec.push_back(x);
}
int count = 0;
int num = 0;
for(int i = 0;i<k;i++){
lst[vec[i]]++;
if(lst[vec[i]]==t)
count++;
}
if(count>0)
num++;
for(int i = 0;i<n-k;i++){
lst[vec[i]]--;
if(lst[vec[i]]==t-1)
count--;
lst[vec[i+k]]++;
if(lst[vec[i+k]]==t)
count++;
if(count>0)
num++;
}
cout<<num<<endl;
}
else
cout<<0<<endl;
}
return 0;
}
#美团##笔试题目##题解#using namespace std;
int lst[10005];
int main(){
int n,k,t;
while(cin>>n>>k>>t){
if(k<=n){
vector<int> vec;
memset(lst,0,sizeof(lst));
for(int i = 0;i<n;i++){
int x;
cin>>x;
vec.push_back(x);
}
int count = 0;
int num = 0;
for(int i = 0;i<k;i++){
lst[vec[i]]++;
if(lst[vec[i]]==t)
count++;
}
if(count>0)
num++;
for(int i = 0;i<n-k;i++){
lst[vec[i]]--;
if(lst[vec[i]]==t-1)
count--;
lst[vec[i+k]]++;
if(lst[vec[i+k]]==t)
count++;
if(count>0)
num++;
}
cout<<num<<endl;
}
else
cout<<0<<endl;
}
return 0;
}
