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

作者: | 更新日期:

团队合作出问题了。

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

零、背景

leetcode 2022 年秋季编程大赛团队赛的时间非常不好,安排在国庆假期的最后一天下午。

由于我是否能参加还不清楚,就没和往年的队友一起组队。
后来,小组内的一个同事问我组队的事情,我便和他一起组队了。

比赛到中间的时候,可能是我电脑的问题,我说话队友听不到,队友说话我也听不到。
最后一小时,有道题我确认队友可以过,但是没联系上对方,于是我便想各自做吧。
最终排名不理想,差几名才能进去前百名。

赛后反思,应该紧抱队友的大腿的,联系补上对方应该及时打电话的。

毕竟这个队友很厉害很厉害。
他的标签有衡水一中、OIer 高考加分、复旦大学、Acmer 金牌等。
而我则是一个平平凡凡的普通人。

以后如果还有机会组团,我想了一个策略。
前面的简单题分工做,而对于后面的难题,我先全部读题并理解题意,并大概判断难度。
如果有难度,则告诉队友题意,队友去想解决方案。
如果多道题都有解决方案,则通过分享屏幕加语音的方式,来给我讲解其中一道题,然后两人分工去敲代码。

总之,有这么厉害的队友,要把队友的优势尽量的发挥出来。

一、最小展台数量

题意:展览持续 n 天,每天各个类型的桌子分别需要若干张。
问最少多少张桌子才能满足活动展览。

思路:不同类型的桌子是互相独立的,所以需要分别求出各个类型桌子的最大值,最后求和即可。

二、装饰树

题意:给一个二叉树,求在所有父子节点之间插入一个 值为 -1的节点,插入的节点方向需要与父子节点保持一致。

注:父子节点方向保持一致含义是,如果是左儿子,则插入的节点需要是左边,左儿子是插入节点的左儿子。

思路:按照题意 DFS 插入即可。

三、美观的花束

题意:给一个数组,求子数组的个数,要求子数组内相同值出现的次数不超过 cnt。

思路:双指针计算即可。

四、Hello LeetCode!

题意:给若干字符串,现在分别从字符串中取出若干字符,最终拼出单词 helloleetcode,求最小代价。

字符串中取一个字符的代价:假设该字符左边有 a 个字母,右边有 b 个字母,则代价是 a*b
注:字符不能复用,即取走后,从字符串中删除。

思路:字符串最多 24 个,字符串长度最大为8, 目标字符串长度为 13,很容易想到状态压缩。

首先,对目标字符串进行状态,即可写出第一个状态和动态转移方程。

状态:dp[k][mask] 前 k 个字符串组成 mask 的最小代价。

状态转移方程: 枚举第 k 个字符串的 mask,求最优值

for(int i = mask; i>=0; i=(i-1)&mask){
  dp(k, mask) = min(dp(k, mask), dp(k-1, mask^i) + dpWord(k, i));
}

现在问题转化为了,一个字符串组成的 mask,怎么求最小代价。

一种方法是预处理每个字符串的所有合法 mask 的最优值,然后 dpWord 直接 O(1) 查找即可。
假设这个预处理可以实现,则第一个状态转移方程复杂度是 O(n * 2^13 * 2^8)

假设一个字符串去的字母固定,最小代价显然是从左右两边取。
所以,可以从左右枚举出一个字符串的所有合法 mask,复杂度 O(n * 4^8)

mask 转化:
预处理字符串时,我们只有每个字符的个数,如何转化为 mask 呢?
有个数,显然需要计数状态压缩。

计数的策略有两种实现。
一种是使用个数,比如 e 字母最多有 4 个,就分配 4 个bit。这样有几个 1 就代表有几个字母。
另一种是使用二进制,比如 e 字母最优有 4 个,分配 3 个 bit,这样最多可以表示 2^3-1 个字符。

两种策略都可以,大家按照自己的喜好去选择就可以了。

注意事项:枚举字符串的 mask 时,枚举量是 2^13,而合法的 mask 是 2^8 个。
为了只枚举合法的 mask,我们预处理的时候,需要把合法的 mask 单独储存下来,这样就可以直接遍历了。

五、沙地治理

题意:给一个包含小三角形的区域,如果一个小三角形相邻的两个小三角形被染色,则当前三角形也可以被染色。
问至少染色多少个小三角形,才能把整个区域都染色。

思路:找规律。

大概如下图,队友找出了规律,分4种情况并通过了这道题。

规律题不涉及算法,我不感兴趣,这里就不展开介绍了。

六、集水器

题意:给一个集水器,中间有一些可以空气可以通过但水无法通过的隔板。
问集水器全部放入水中,再捞起来,能够剩余多少水。

隔板如下:

思路:

朴素的思路是先 DFS 填充水,再 DFS 让水流走。

不过有个问题:空气可以穿过隔板,即连通器里水的高度不能高度最低出口的高度。

面对这个限制,标准的做法是使用并查集维护连通器,并记录连通器的最低出口高度。
这样,新的水合并进来之前,先判断是否高度出口,高于了,就需要把水放走。

队友说其实可以不使用并查集,一个 BFS 就可以了。
我一想,确实可以,递归的时候维护遇到的最低出口即可。

最终两个算法我都实现了一下,代码也都通过了。

我的代码上传到 github 上了,感兴趣的可以自己去看代码。

https://github.com/tiankonguse/leetcode-solutions/tree/master/other/season/2022-fall/team

七、最后

这次比赛是两个人,幸亏队友比较给力,第五题做出来了,最终排名一百出头。
如果当时沟通没出问题,第四题队友的实力肯定也可以做出来,这样排名应该可以到达 80 左右。

回顾六道题,前三题难度太简单,后三题难度瞬间飙升,比赛的体验非常不好。

加油,算法人。

《完》

-EOF-

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

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

点击查看评论

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

tiankonguse +
穿越