Leetcode 第141场比赛回顾

零、背景

Leetcode 第 141 场比赛的题目难度属于中等偏下难度。

第二题题意理解起来有点费劲，可能会浪费一些时间，其他题就是拼手速了。

接下来就看看看这四道题吧。

一、重复零

题意：给一个数组，如果数组某个位置值是 0 ，则在其后面插入一个 0 ，后面的元素整体后移。

要求：数组的长度不能变化。

思路：这里数组长度不能变化的意思就是，每插入一个 0 ，最后一个元素就需要从数组中删除。

比赛期间，最简单粗暴的方法就是定义一个新的数组，循环处理即可。

而作为算法题，我们就需要考虑如何做才能最优。

这里最优的方法是使用 O(1) 的空间和 O(n) 的时间，即不适用额外的数组并循环一遍做出这道题。

对应的思路是预处理，计算出最终要插入多少个 0 ，并计算出要后移的最后一个位置。

这里有一个注意点是，最后一个位置可能是 0 ，然后刚好长度不够了，最后一个 0 不需要插入 0 了。

对于这种情况特殊判断一下即可。

二、标签的最大值

题意：给一个集合，每个元素有一个值 values[i] 与标签 labels[i] 。

这里要选择一个子集，使得子集的元素个数不超过 num_wanted ，而且相同标签的元素个数不超过 use_limit 。

求子集的最大和。

思路：这里第一步是要读懂题意，我反复读了十遍题目，结合数据样例终于看懂题了。

关键点在于这句话 For every label L, the number of items in S with label L is <= use_limit. 。

含义是子集里面，相同的标签有一个个数限制，即不超过 use_limit 个。

题意理解了，代码就好做了。

第一种方法是先使用 map 对标签进行聚合，相同标签的元素，按 value 值从大到小排序。

然后对于每个标签，选出 top use_limit 大的值，选出的所有值里面再选择最大的 num_wanted 个。

具体代码实现的时候，我定义了一个节点结构体，然后二维排序。

然后遍历 排序 后的数据，对每个标签挑选出 top use_limit 的元素放入到优先队列里面，最后从优先队列里面取 num_wanted 个最大值即可。

这里优先队列也有两个选择。

使用最大堆的话，所有合法的元素都进入堆，最后从堆中选择 num_wanted 个元素即可。

使用最小堆的话，当堆里元素大于 num_wanted 个时，就需要把最小值出堆。这样就可以保证堆里面的元素只有 num_wanted 个，最后求和即可。

还有一种简洁的方法是直接使用 pair<label, -value> 储存这个数据，这样就可以直接排序了。

默认是升序的， value 使用负数，这样最大的 value 就会在最前面了。

之后的和上面一样，每个标签里选前 use_limit 个值，最终再选 num_wanted 个值。

看别人的解题报告时，发现有人使用 pair<-value, label> 来储存数据并排序，然后使用 map<label, count> 来计数。

这样累计选择 num_wanted 个满足要求的元素即可。

三、矩阵上的最短路

题意：给一个 N*N 的矩阵，值为 0 代表有一个顶点，上下左右八个方向存在 0 则代表两个顶点间有条边。

问是否存在一条路径可以从左上角到达右下角，如果存在输出最短的路径长度。

思路： BFS （广度优先搜索）即可。

从左上角开始搜索，如果搜到右下角了，则说明可以到达，搜索的深度就是长度。

注意事项是：起点和终点需要是顶点。

四、最短的公共父序列

题意：给两个字符串 str1 和 str2 ，这两个字符串同时是字符串 S 的子序列，求最短的字符串 S 。

思路：想要字符串 S 最短，则说明 str1 和 str2 组合为 S 时，相同的字符应该尽量合并为一个字符。

能够合并的最大的相同字符就是两个字符串的最长公共子序列。

所以这道题需要求出最长公共子序列，然后构造出答案。

而且可以确定答案的长度就是 len(str1) + len(str2) - commSubSeq(str1, str2) 。

这里的最长公共子序列需要记录其路径，由于是使用二位数组计算的，路径天然存在。

所以我们只需要逆向的遍历路径，构造出答案即可。

当然直接在路径上构造答案可能比较抽象，一种简单的方法是先求出最长公共子序列，然后根据子序列来构造答案。

至于怎么构造，建议画一个图可能会清晰一些，简单来说就是遇到相等字符之前，随意构造，相等了同时减一。

这里我想到一个扩展题：求满足要求的答案的个数。

这个其实也很简单，我们只需要在上面记录的路径上再次进行DP，就可以求出所有合法路径的个数了。

五、最后

回头看看，这次比赛题挺好的，难度适中，大家花一些时间思考一下，做出四道题应该是没问题的。

四道题解在 leetcode 上我也分享了，刷题的朋友可以帮我点个赞，虽然我不知道 leetcode 上点赞有啥用。

地址：https://leetcode.com/tiankonguse/

-EOF-