Leetcode 第137场比赛回顾

零、背景

Leetcode 第136场比赛的题其实很不好，前三题太简单，第四题则是想到则会，想不到则很难的题。
下面我们来看看吧。

一、最后一块石头的重量

题意：有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块最重的石头，然后将它们一起粉碎。
如果两个石头重量不相等，剩余的重量会当做新的石头放在这堆石头里。
问当不能操作时，这堆石头的重量。

思路：使用堆这个数据结构来快速找到最大的石头即可。
在C++的STL里面，名字叫做优先队列。

二、删除字符串中的所有相邻重复项

题意：字符串里相邻两个字母如果相等，可以同时删除。
问最后不能再删除时的字符串。

思路：就像括号匹配，维护一个栈即可。

三、最长字符串链

题意：如果一个字符串 A，在任意一个位置插入一个字符，能够形成另外一个字符串 B，则称 A 是 B 的前身。
若干个字符串，如果能从第一个依次形成下一个字符串，则这些字符串称为词链。
求词链的最大长度。

思路：预处理字符串，构造出一个图，字符串是顶点，如果一个是另一个的前身，则有一个单向路径。
然后 DP 求出每个字符串为起点的最大路径长度。
答案则是这些路径长度里最大的那个。

注意：DFS的时候，通过 DP 来防止计算过的节点重复计算。

四、最后一块石头的重量 II

题意：有一堆石头，每块石头的重量都是正整数。
每次可以任意选两块石头进行粉碎。

如果重量相等，则两个石头都粉碎。
如果重量不相等，则差值是合并后的石头重量。
问最后这堆石头的最小重量。

思路：比赛的时候在思考二分以及剪枝搜索，发现一直行不通。
赛后看到有人说是 DP，然后恍然大悟。

关键思想：对于一堆石头，比如四个，有很多种组合可能，哪种是最优值我们是不知道的。
比如石头分别是 A <= B <= C。

则有这些组合情况：

A - (C - B)
B - (C - A)
C - (B - A)

简化一下就是：

+ A + B - C
+ A + B - C
+ A - B + C

这里可以看到，一堆石头的合并可以看做有一堆括号的加减运算。
而我们把括号全部展开后，就是一堆石头是加号，一堆石头是减号，目标是求绝对值最小。

加号的石头放在一起，减号的石头放在一起，问题就转化为了：将这堆是有分成两部分，总重量差最小。
妈呀，这不就是最基础的背包问题吗？

考虑到物品只有 30 个，每个石头重量不超过 1000，总重量不超过 3万，直接暴力枚举所有加减符号即可。

注：由于是最小值，也可以使用石头总和的一半来过滤显然不是答案的数据。
不过数据量这么小，这里就不过滤了。

五、最后

这次比赛，第一题我没有使用优先队列，使用的是multiset，结果发现删除的时候，一下就把所有相同的删除了，而不是删一个，被坑了一下。于是我改成map计数过的
第二题随手过了。
第三题在判断是不是前身时，copy错了一个判断语句，WA了一次。
最后一题就没想法了。

另外，为了提高后续的编码速度，我将常用的函数收集在了模板文件base.h内。
大家如果使用我的模板的话，可以来看这个来提高效率。

-EOF-