美团暑期实习

只留下了后两道编程题。。。不过据说前两个编程题比较简单

编程题03 - 众数

具体题我就不抄了.. 大概意思是求滑动窗口（长度为k）内的所有最小众数（只有一个众数直接输出，有多个众数出现次数相同-> 输出最小的）

具体方案是维护这样一个数据结构：

hash: 维护窗口内每个元素的出现次数
vector<set<int>> A : 对于每个出现次数i而言 A[i]存放出现次数为i的所有元素

这样在进入窗口和弹出窗口的时候更新一下这两个就好了

void modify(vector<set<int>>& A, unordered_map<int, int>& hash, int val,  bool is_add)
{
    A[hash[val]].erase(val);
    if(is_add) hash[val]++;
    else hash[val]--;
    A[hash[val]].insert(val);
}

vector<int> solution(vector<int>& nums, int k)
{
    vector<int> res;
    unordered_map<int, int> hash;
    vector<set<int>> A(k + 1); // 出现次数为i的元素所在的集合
    for(int l = 0, r = 0, max_cnt = 0; r < nums.size(); r++)
    {
        modify(A, hash, nums[r], true);
        if(hash[nums[r]] > max_cnt) max_cnt = hash[nums[r]];
        if(l < r - k + 1)
        {
            modify(A, hash, nums[l++], false);
            if(A[max_cnt].empty()) max_cnt--;
        }
        if(r >= k - 1) res.push_back(*A[max_cnt].begin());
    }
    return res;
}

编程题04 - 树上DP

美团图论和dp是必考的得了这回考了个图论+dp的结合

具体题的意思: 给定一棵树，每一个节点有一个权重，选择其中某些节点，满足被选中的节点两两不相邻，求在所有的选择方案中，最大化被选择节点权值之和的情况下，被选择节点权值最小值尽可能大。

输入

第一行两个整数N和M，分别表示树的节点数和边数第二行为N个整数，分别表示每个节点的权重接下来M行，每行两个整数a和b，存在一条从a到b的边。

输出

输出两个整数，表示能选择的最大权值之和是多少，以及权值最小值是多少，用空格分割。

输入样例

输出样例

16 3

基础就是 树上一条边只能选一个节点，求权值最大 可以说是树上DP的经典题了

这题比我做过的树上DP还要怪我开始也没反应过来那个最大化被选择节点权值之和的情况下，被选择节点权值最小值尽可能大是啥意思

后来发现是在两个子节点权值一样选哪个都可以的时候，选哪个权值大的child

剩下的建图和DFS（是的树上dp都是dfs写的）都是很经典的套路了

f[i, 0] 表示不选node[i]的最大方案
f[i, 1] 表示选node[i]的最大方案

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int val[N];
int f[N][2], minv[N][2];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++; 
}

void dfs(int u, int father)
{
    f[u][1] = val[u];
    minv[u][1] = val[u];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs(j, u);
        // // 一般处理
        // f[u][1] += f[j][0];
        // f[u][0] += max(f[j][1], f[j][0]);
        f[u][1] += f[j][0];
        minv[u][1] = min(minv[u][1], f[j][0]);
        // 带最大值的更新
        f[u][0] += max(f[j][0], f[j][1]);
        if(f[j][0] > f[j][1])
            minv[u][0] = min(minv[u][0], minv[j][0]);
        else if (f[j][0] < f[j][1])
            minv[u][0] = min(minv[u][0], minv[j][1]);
        else
            minv[u][0] = min(minv[u][0], max(minv[j][0], minv[j][1])); // 如果f一样 就挑大的
    }
}
int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", val + i);
    // 1. 建图
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    // 2. 树上dp
    dfs(1, -1);
    if(f[1][0] > f[1][1])
        cout << f[1][0] << ' ' << minv[1][0] << endl;
    else
        cout << f[1][1] << ' ' << minv[1][1] << endl;
    return 0;
}

Previous美团2021笔试通用卷10

Last updated 3 years ago