leetcode 第 340 场算法比赛
作者:
| 更新日期:最后一题至少有四种方法,你用的什么方法呢?
本文首发于公众号:天空的代码世界,微信号:tiankonguse
零、背景
这次比赛最后一题大意了,错了两次,排名一百名左右了。
一、对角线上的质数
题意:问两条对角线上最大的质数是多少?
思路:先打质数表,然后循环判断求最大值即可。
二、等值距离和
题意:给一个数组,求相等的数字集合里面,当前下标与其他所有下标的距离之和。
思路:经典题型,比赛经常遇到,比如上上周的《第 338 场周赛》的第三题就是这种题型。
先对相同值的下标进行分组,然后维护左右个数与左右和即可。
具体来说,有两种做法。
方法1:维护左半部的前缀和 与 后半部的前缀和,则可以通过前缀和与矩阵求差,则可以求出距离和。
方法2:直接维护左半部的距离和 与 右半部的距离和,代码见《第 338 场周赛》第三题题解。
三、最小化数对的最大差值
题意:给一个数组,问选择 p 对二元组,怎么选择才能使得选择的二元组的最大差值最小。
思路:求最大值的最小值,典型的二分题。
直接二分答案,判断满足答案的二元组是否大于等于 p 即可。
四、网格图中最少访问的格子数
题意:给一个矩阵,从左上角走向右下角,求经过的最少方格数。
规则:当前网格值是 x ,则一次最多只能向左或向右走 x 距离。
思路:与上次比赛一模一样,BFS 搜索即可。
唯一的问题与上次比赛最后一题也一样,数据量有点大,可能会超时。
我们需要维护一个数据结构,从一个网格移动到下一个网格时,需要快速跳过已经访问过的网格。
方法1(大部分选手做法):有序集合。
参考上次比赛,维护一个有序集合 SET,直接二分查找即可。
方法2(第二名做法):线段树或者树状数组。
快速找到区间内第一个值为 1 的位置。
方法3(第六名做法):从后到前贪心。
从后到前遍历,快速跳到答案。
方法4(我的做法):并查集。
每一行与每一列都维护一个并查集,快速找到下一个未出现的位置。
注意事项:遍历的时候,每一次都需要查询并查集,快速跳到下一个位置。
方法5(第七名做法):从前到后贪心。
对于同一行,如果行与列分开看,可以证明,不管是使用有序集合,还是线段树与树状数组,还是并查集,最终都是得到一个前半部为已访问,后半部为未访问。
因为,每一行与每一列维护一个最大值即可。
PS:我第一个代码就是维护一个最大值,由于行与列混合在一起,导致 WA 一次。
五、最后
最后一题有无数种方法,你用的什么方法呢?
《完》
-EOF-
本文公众号:天空的代码世界
个人微信号:tiankonguse
公众号ID:tiankonguse-code
本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。