leetcode 秋季编程大赛(2021团队赛)

作者: | 更新日期:

被 leetcode 坑了,暴力反而通过,优化后超时。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

leetcode 的秋季个人赛我忘记参加了,团队赛就留意了下日期。

团队里两个队友本来都在美国。
下午三点开始比赛的时候,他们那边是凌晨十二点。

今年有一个回国了,但恰好今天要去参加婚礼。

于是团队赛只剩下两个人了。

两个人有六道题,最终只做出前四道题。

最后一题想了一个O(n * log(n)^2) 复杂度的算法,总是超时。
最后换成O(n^2 log(n)) 的暴力算法,结果通过了。

leetcode 的数据有问题呀。

一、开幕式焰火

题意:给一个二叉树,问二叉树中节点值组成集合后,集合的大小是多少。

思路:递归遍历二叉树,放进集合,输出集合大小即可。

通过者:队友网速快,先看的第一题,我便不看这道题了。
通过时间:0:02:01

PS:队友手速好快。

二、自行车炫技赛场

题意:给一个二维坐标,坐标有两个属性:高度和减速带。
相邻坐标之间移动时有个速度转移公式。
现在给一个起始坐标和速度,问在速度不为 0 的情况下,哪些坐标的速度可以到达 1。

思路:坐标大小为100*100,根据公式可以知道最大速度为 200
坐标与速度组合最多有 100*100*200个状态。
DFS 求出所有合法状态即可判断有多少个答案。

通过者:由于队友做的第一题,我便做的这道题题。
通过时间:0:23:14

三、志愿者调配

题意:给一个无向图和若干个操作,操作分三类。

操作1:顶点 x 的权重值减一半。
操作2:顶点 x 相邻顶点的权重值都加上顶点 x 的权重值。
操作3:顶点 x 相邻顶点的权重值都减去顶点 x 的权重值。

现在我们知道初始状态所有顶点的权重值之和,以及最终状态除了第一个顶点外其他顶点的权重值。
求初始状态每个顶点的权重值。

思路:假设最终状态第一个顶点的权重值为 x。
所有顶点都使用 a * x + b<a, b> 二元组标示。

然后逆向遍历操作,并做逆向计算。

逆向操作1:顶点 X 的权重值翻倍。
逆向操作2:相邻顶点都减去 逆向操作3:相邻顶点都加上

最终可以得到初始状态所有顶点的二元组,求和后得到一个一元二次方程。
解方程可以计算出 x 的值。

初始状态所有顶点的公式都套入 X,即可计算出户所有顶点的初始值。

小技巧:二元组可以封装为一个对象,并实现加法和减法,翻倍等价与加法。

struct Node{
    ll a, b;  // a * x + b
    
    void Add(Node& o){
        a = a + o.a;
        b = b + o.b;
    }
    void Minute(Node& o){
        a = a - o.a;
        b = b - o.b;
    }
};

通过者:队友
通过时间:0:34:51

四、入场安检

题意:有 n 个安监室,每个安监室可以容纳若干个人,这些人需要排队。
排队方式可能是队列的形式(先进先出),也可能是栈的形式(后进先出)。

现在问这些安监室如何选择排队方式,可以使得第 k 个人经过所有安监室后变成第一个人。

思路:题意的大概意思很容易理解,但是细节很难理解。

我有两处理解错题意了。

第一处时栈如何出队的。
假设一个安监室大小为 a,我理解为 a 个人先入栈,然后 a 个人在同时出栈。
结果是这 k 个人顺序反转。

第二处时最后那批人,没有把安监室填充慢该怎么办。
我起初理解为不满时,按不满继续处理。

三十分钟过去了,代码也敲完了,已测试,第一组测试数据不对。

再反复读题意,发现题目增加了一个注意实现,最后那批人永远出不去了。

而对于栈,看了题目提供的动图,发现每次只能出栈一个人。
这意味着栈中的人,除了最顶端的人,其他人永远都出不去了。

理解题意后,这道题反而非常简单了。

输入的位置为 K。
每经过一个房间,有两种选择,位置就拆分为两种状态。

房间个数为 200,意味着选择有 2^200中情况。
每个房间最多容纳 200 人,总人数最多可能是 40001 人,位置状态也就是 4 万个。

储存一个房间每个状态的路径数,我们就可以计算出下个房间每个状态的路径数。
复杂度:O(200^3)

int N = M + 2;

int now = 0;
dp[now][k] = 1; 

for(int i = 1; i <= n; i++) {
    int c = capacities[i-1];
    
    int nxt = 1 - now;
    dp[nxt].clear();
    dp[nxt].resize(N, 0);
    
    for(int k = 1; k < N; k++) { // k 下标从 1 开始
        if(dp[now][k] == 0) continue;
        
        // 最后一个人还没进去,可以出队
        if(preSum[i] + k <= M + 1) { 
            dp[nxt][k] = (dp[nxt][k] + dp[now][k]) % mod;
        }
            
        // 最后一个人还没进去,可以出栈
        if(k != M + 1 &&  k >= c) {
            int tmp = k - (c - 1);
            dp[nxt][tmp] = (dp[nxt][tmp] + dp[now][k]) % mod;
        }
    }
    
    now = 1 - now;
}

return dp[now][1];

通过人:我做的这道题。
通过时间:1:24:32

五、无限棋局

题意:给一个五子棋的无限坐标棋盘,问接下来三步内(黑、白、黑),是否可以决出胜负。
如果可以输出胜者,否则输出平局。

思路:三步分别处理。

胜利点定义:一个位置放入棋子后,该颜色的棋子组成一条连续的线,且至少有 5 个。

第一步最简单,只要找到一个胜利点则认为胜利,复杂度O(n^2)
第二步比较简单,至少有两个胜利点,复杂度O(n^2)

第三步稍微复杂点,需要第一步填充某个坐标后,构造出至少两个胜利点。
构造胜利点的时候,分两种情况:连续构造与隔空构造。

连续构造比较好理解。
已经有一个三点成线了。
增加一个点,就是四点直线,两端就是两个必胜点。

隔空构造意味着增加一个点后并没有组成四点直线,而是一点与三点或者两点与两点。

六、环形闯关游戏

题意:给一个环形关卡,每个关卡有一个权重值。
起始状态有一个分数,可以任意选择一个关卡来挑战。
如果分数大于挑战关卡的权重值,分数可以与关卡的权重值合并得到新的分数。
然后挑战过的关卡的相邻关卡也可以进行挑战。

问起始状态的分数最低是多少时,依旧可以调整所有关卡。

思路:我很快就想到解决方法了。

首先是从高到底枚举 bit 位,判断组成的分数是否可以通过所有关卡。

例如假设处理到底 i 位,已经有前缀 preAns 了。
优先判断第 i 位为0时是否有答案,即判断 preAns + (1<<i) - 1 是否有答案。
如果有答案了,这个答案肯定比第 i 位为 1 时的答案更优。
枚举复杂度:O(log(n))

那得到一个分数后,怎么判断是否是答案呢?
我的方法依旧是枚举。
枚举起始位置为所有位置,判断是否有某个位置可以通过所有关卡。
枚举复杂度:O(n)

那得到起始位置和起始分数了,怎么判断是否可以通过关卡呢?
我的方法是通过线段树二分查找来解决。

每次尝试向左与向右,找到最远的区间最大值不大于当前分数位置。
如果有找到,再求区间 bit 或运算的结果,累计到当前分数上。
之后再次尝试向左与向右寻找是否可以走的更远。
复杂度:log(n)^2

综合复杂度:n log(N) log(n)^2

当然,这个方法看着很巧妙,但是最终超时了。

赛后看了有人没有使用线段树,直接加一减一去寻找答案的。
暴力的复杂度是n^n log(N),试了下,然后竟然过了。

赛后还看到有人使用并查集过的,后面有时间了研究下为啥可以使用并查集。

七、最后

这次比赛还不错的。

第一题是签到题。
第二题是记忆化搜索。
第三题是计算题。
第四题是动态规划。
第五题是模拟题。
第六题是二分加其他数据结构体。

最后一题被卡超时了,比赛的时候我没去看倒数第二题。
如果再多一个队友的话,两道题应该都不成问题吧。

加油,算法人。

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越