Leetcode 第141场比赛回顾
作者:
| 更新日期:动态规划、广度优先搜索、排序与构造,都是基础知识。
本文首发于公众号:天空的代码世界,微信号:tiankonguse
零、背景
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-
本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。