leetcode 2021 春季团队编程大赛

零、背景

2021年04月10日，参加了 lleetcode 2021 春季编程大赛团队赛。

总的来说，这次比赛题都还好，但是我们剩一道题有想法，时间不够了。

最终排名 37 名，还不错的，和 11 名的奖品都一样。

一、蓄水

题意：给 n 个水桶的初始容量，以及 n 个水池的目标容量。

现在有两个操作：
1）选择一个水桶，容量加1。
2）将所有水桶接满水，倒入到相同编号的水池中。
问至少操作几次，可以把水池倒满水。

思路：简单分析一下，可以发现肯定是先不断进行操作1，然后不断进行操作2。
因为假设有一个操作1在操作2后面，那将操作1放到前面后，对应的水池可以倒入更多的水。

顺序确定了，加下来就是选择如何贪心了。

枚举操作2，目标容量除以操作次数，就知道每个水桶操作1至少需要操作多少次。
复杂度：O(100 * n)

int storeWater(vector<int>& bucket, vector<int>& vat) {
    if(accumulate(vat.begin(), vat.end(), 0) == 0){
        return 0;
    }
    int n = vat.size();
    int ans = 0x3f3f3f3f;
    for (int i = 10000; i >= 1; i--) {
        int tmp = i;
        for (int j = 0; j < n; j++) {
            if (vat[j] == 0) continue;
            int need = vat[j] / i;
            if (need * i < vat[j]) need++;
            tmp += max(0, need - bucket[j]);
        }
        ans = min(ans, tmp);
    }
    return ans;
}

从操作1贪心的话，需要每次找到操作2最大的水桶，然后进行一次操作1。

可以使用优先队列来维护每个水桶操作2的次数，这样就可以不断的贪心选择操作1。
复杂度：O(100 * n * log(100))
这样做会超时。

优化：上面的贪心之所以会超时，是因为贪心进行操作1之后，这个水桶的操作2次数可能没变化。
没变化意味着这次贪心之后，下次的最大值还是自己。

例如水池大小是 10，水桶大小是 6，需要两次操作2。
贪心选择1后，水桶大小是 7，依旧需要两次操作2。
再次贪心选择1后，水桶大小是 8，还是需要两次操作2。

所以可以直接计算出需要多少次，使得操作2的次数减一。
复杂度：O(100 * log(n))

代码比较长，这里就不贴了，大家可以去原文看源代码。

二、二叉树染色

题意：对一个二叉树进行染色，要求连续节点最多可以染 k 个。
问怎么染色，可以使得染色的节点值之和最大。

思路：动态规划题。
状态定义：当前子树最多可以染色 k 个颜色的最优值。

状态转移分几种情况。

1）当前节点不染色，则两个子树最多染色的个数重置。
2）当前节点染色，枚举左右儿子的染色数的答案，求最大枚举值。

class Solution {
    map<pair<TreeNode*, int>, int> m;
    int K;
    int dfs(TreeNode* root, int k){
        if(!root) return 0;
        
        pair<TreeNode*, int> p = {root, k};
        if(m.count(p)){
            return m[p];
        }
        
        int ans = dfs(root->left, K) + dfs(root->right, K); // 当前不染色
        for(int l=0;l < k;l++){
            int r = k - 1 - l;
            int tmp = dfs(root->left, l) + dfs(root->right, r) + root->val;
            ans = max(ans, tmp);
        }
        return m[p] = ans;
    }
public:
    int maxValue(TreeNode* root, int k) {
        K = k;
        return dfs(root, K);
    }
};

三、电动车游城市

题意：有n个城市，给你城市间的距离以及每个城市充电桩的充电速度。
问一个特斯拉电车，从起点到终点最少需要多少时间。

思路：动态规划题。
状态定义：f(n, v) 电车在城市n且有电量 v时，到达终点的最短距离。

考虑到城市间存在环，无法写状态转移方程。
所以需要使用搜索来做这道题。

搜索的时候，相同状态如果遇到更优值，则加入队列继续搜索。
最坏情况下，每次队列都是最差值，最多重复入队 n 次。
复杂度：O(n * n * v)

优化：队列改成优先队列。
这样每次都是路程最短的状态出队，避免无效状态重复入队。
复杂度：O(n * v)

四、最多牌组数

题意：给 n 个数字，我们可以选三个相同的数字，也可以选三个连续的数字。
问最多可以选出多少组。

思路：动态规划。

普通状态：f(n, use1, use2) 代表第 n 个位置被顺子占用了 use1 个位置，第 n-1 个位置被顺子占用了 use2 个位置的最优值。

状态转移：枚举第 n 个位置的所有顺子，求最优值。
复杂度：O(n^3)

贪心优化：如果第 n 个位置的顺子超过或等于 3 个，每 3 个顺子等价与 3 个组连续的相同数字。
复杂度：O(n * 3 * 3)

五、最小矩形面积

题意：给 n 条直线，问所有交点可以使用与坐标轴垂直的矩形覆盖起来。
求最小的矩形面积。

思路：想要矩形最小，肯定是矩形的四条边恰好覆盖最外层的交点。
所以问题转化为了求上下左右四面的最大值交点。
这里不妨来求 y 坐标轴的最大值。

由于输入的直线 y = kx + b 中的 k 大于 0，所以直线都是从左下到右上的。

我们枚举一条直线，可以发现与这条直线夹角最小的直线，交掉会最远。
所以可以按斜率 k 对所有直线排序，如果斜率相同，则按偏移量 b 排序。

这样，只需要计算相邻两条直线的交点，求最大值即可。

潜在的问题：假设斜率 k1 < k2 < k3。
会不会由于 b 的关系，使得k1 & k3 的交点比 k1 & k2 更优呢？
纸上画画图，发现，假设存在这种情况，我们会发现此时k2 & k3 会比 k1 & k3 更优。
所以即使存在这种情况也不会影响最优答案。

六、守卫城堡

题意：给一个 2*N 的地图，地图上有若干障碍物、若干怪兽出生地、若干传送点、一个城堡和若干空地。
若送点之间可以任意传送，问最少在空地添加几个障碍物才能阻止怪兽到达城堡。

思路：本来想枚举所有情况，却发现情况太多无法枚举。
然后我想到，可以构造出一个图来，然后使用图论解决这个问题。

若干怪兽出生地可以缩点为一个点，称为出发点。
多个传送点可以缩点为一个特殊的空地。
城堡称为目的点。

根据传送点与出发点、目的点的关系，分四种情况。

第一种：传送点同时与出发点和目的地挨着，则没有答案。
第二种：传送点只与出发点挨着，此时传送点和出发点可以缩点。
第三种：传送点只与目的地挨着，此时传送点和目的地可以缩点。
第四种：传送点是独立的，则传送点互连的顶点之间可以分别加一个边，然后删除传送点。

这样处理之后，就是一个简单的图，从起点到终点可能有若干路径。
我们需要找到删除哪些顶点，可以使得起点到达终点不连通。

这个就是最大流问题，队友敲了一个最大流，改了改就过了。
我不懂最大流，就不过多介绍了。

七、最后

这次比赛题都不难，时间再多半个小时最后一题应该就可以通过了，不过无所谓了。

总的来看这次比赛
第一题枚举或贪心
第二题动态规划
第三题广搜
第四题动态规划
第五题贪心
第六题图论最大流

除了最后一题，其他题我都会做。
最后一题看其他人的代码也有动态规划的，后面再研究下怎么动态规划怎么做。

你参加这次比赛了吗？
都做出了哪些题，分别都是怎么做的？

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code