Leetcode 第154场比赛回顾

零、背景

这次比赛最后一题是一个赤裸裸的图论模板题。
然而我专攻的是数据结构分类，而面对图论题，我就有点手忙脚乱。
一心想着找个模板贴上去就行了，结果找了四五个模板都没通过这道题。

赛后发现这道题其实很简单，现场学习这个算法也就几分钟的事情。
于是赛后我才过了最后一道题。

一、统计 Balloons 的个数

题意：给一个字符串，问可以组成多少个Balloons。

思路：统计每个字母出现的个数。
对于bans这些字母，统计出现的最小次数。
而对于lo这些字母，统计出现的最小次数并除二。
最终两个最小值取min。

二、括号内内容反转

题意：给一个有括号的字符串，括号展开意味着将括号内的内容反转。
求最终括号展开后的字符串。

思路：括号展开问题，就是栈的问题。

分析：遇到左括号了就使用栈保存之前的数据，遇到右括号了，就反转、出栈拼接两个字符串。

PS：当然，直接字符串拼接复杂度较高。如果数据量大了，可以考虑使用链表来解决拼接的性能问题了。

三、重复序列的最大序列和

题意：求序列S重复K次组成序列的最大子序列和。

思路：最原始的做法是拼出展开后的序列，然后使用动态规划求答案。
但是看到 S和K都是 10^5的数量级，序列展开后就是10^10的数量级，内存都爆了。
所以这里不能全部展开。

分析一下可能的答案，发现分两种情况。

如果序列S的总和小于等于0，我们只需要关心两个S即可，后面的都没用。
毕竟多一个S总和就会减少一点。
此时答案就是两个序列S拼接后的最优答案（经典的最大连续子序列）。

PS：此时答案分两种情况，一种直接是原始S的一个子序列，一种是第一个S的后缀加第二个S的前缀。

而序列S的总和大于0时，则中间所有的序列S都加上去答案可能更大。
此时，两头的序列，需要取前缀和后缀的最大值。

总结一下就是分三种情况：

1、原始S串求最大子串和。
2、两个S串求最大子串和。
3、最大前缀和、最大后缀和、k-2个S串三者总和。

情况二分两种情况，一种是答案在S上，一种是答案是最大前缀和加最大后缀和。 后一种又和情况三类似，所以可以和情况三合并在一起计算。
这样就可以做出这道题了。

四、图的割边

题意：给一个无向连通图，求所有割边。
割边定义：删除这个边，连通图就不再联通，即顶点被划分为两个独立部分。

思路：模板题，虽然我ACM出身，但是五六年来都没有怎么学习过图论题。
所以网上找好几个模板，发现都有问题，调了一个小时也没通过测试样例。

PS：实际上不应该找模板的，直接自己推理可能也早做出来了。

赛后，花了10分钟了解了一下 Tarjan 算法，然后五分钟就把这道题过了。

Tarjan 思想：对于一个连通图，递归可以访问到所有顶点和边。

而对于割边，例如2-4，递归的时候，2-4递归的所有顶点都大于2。
而对于非割边，比如5-6，递归的时候，6可以找到更小的4。

总结一下就是，这个边递归找的最小编号都比自己大，那这个边就是割边，否则不是割边。

所以我们需要做的就是递归寻找每个顶点能够到达的最小编号，然后比大小即可。

五、最后

这次比赛最后一题没做出来也符合预期。

之前曾在《算法：专业选手与业余人员的差距》介绍过， leetcode 上的算法一般都是数据结构题， 这次一反常态出现一个图论题，平常擅长数据结构的人就做不出这道题了。

比如论坛排名第一的就是批判这道题的讨论。

当然，Tarjan算法这个思想还是比较不错的，本来是图论题，转换成了纯粹的数据结构题了。

-EOF-

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