美团后台开发笔试编程题代码

1.图的遍历

答案就是所有边的两边然后减去离1最远点到1的距离

// 图的遍历
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
vector e[N];
int ans;
void dfs(int x, int fa, int w) {
    for(auto to : e[x]) {
        if (to == fa) {
            continue;
        }
        dfs(to, x, w+1);
    }
    ans = max(ans, w);
}
int main() {
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 0; i < n; ++ i) {
            e[i].clear();
        }
        for(int i = 1; i < n; ++ i) {
            int x, y;
            scanf("%d%d", &x, &y);
            e[x].push_back(y);
            e[y].push_back(x);
        }
        ans = 0;
        dfs(1, -1, 0);
        // cout << ans << endl;
        printf("%d\n", (n-1)*2-ans);
    }
    return 0;
}

2.区间统计

直接扫描一下区间就可以了

// 区间统计
#include <bits/stdc++.h>
 using namespace std;
typedef long long ll;
const int N =1e5+5;
int cnt[N];
int a[N];
int main() {
    int n, t, k;
    while(~scanf("%d%d%d", &n, &k, &t)) {
        memset(cnt, 0, sizeof(cnt));
        ll res = 0;
        ll ans = 0;
        for(int i = 1; i <= n; ++ i) {
            scanf("%d", &a[i]);
            cnt[a[i]] ++;
            if(cnt[a[i]] == t) {
                ans ++;
            }
            if(i >= k) {
                if(ans > 0) res ++;
                cnt[a[i-k+1]] --;
                if(cnt[a[i-k+1]] == t-1) {
                    ans --;
                }
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}