leetcode 第181场算法比赛

作者: | 更新日期:

考查细节的时候到了。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

这次比赛有点 acm 的味道了,有很多边界需要考虑了。

一、按位置顺序构造数组

题意:给一个序列,序列的值是在指定位置插入一个值。求最终的数组。

思路:直接使用 vector 的 insert 即可。

注意事项:insert 是在指定位置插入,所以如果在最后插入,就需要 push_back 了。

二、四因数

题意:如果一个数字只有四个因子,则成为四因数。求这些四因数所有因子之和。

思路:分两步。

第一步判断是不是四因数。
第二步求因子之和。

考虑到 1 和 数字本身也是一个因数,那不考虑这两个因子的话,内部只能有两个因子。

显然,如果两个因子都是不相等的素数,那显然就是答案了。

比如 35 = 15,15 显然是四因数。
而 3
3 = 9, 9 不是四因数,因为内部只有 1 个因子。

这里大家都可以考虑到。
但是有一个特殊情况也是四因数,很容易被忽略。

这种情况就是 333 = 27,也是两个因子 3 和 9。
而 333*3 = 81 则有三个因子 3,9, 27,不满足。

所以对于素数因子的三次方恰好等于输入数字时,也是四因子。

考虑到这几种情况,我们一般就可以做出这道题了。

什么。你超时了?
请提前预处理计算出所有的素数。

三、有效路径

题意:给6种管道(如下图),地图中每个位置是什么管道已经确定了,问能否从左上角到达右下角。

这道题虽然是搜索题,但在 ACM 中也属于模拟题,因为代码量巨大。
我敲代码慢,所以选择先去做第四题,然后再做第三题。

思路:既然是路径是否存在题,BFS 即可。

BFS 需要使用 队列来储存需要遍历的点,还需要一个 set/map 来标记这个点是否走过来防止死循环。

有人会有疑问:管道路径不是只有一条吗?那队列里是不是永远只有一个值了。
大部分情况下是这样,但是对于管道4,会有两种情况。

面对边界很多的情况,大部分人是写一堆 if/else 或者 switch。
这里给大家分享一个我常用的方法,面试中使用这个方法会给你加分的。

面对这道题,我还有个疑问:路径经过右下角算不算有答案。

英文的原题描述是:”A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). “

中文描述是“网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径”。

重点在于,ends at the bottom-right cell,经过算不算 end 呢?
没办法,只能两种题意都提交一下,看运气了。


四、最长快乐前缀

题意:给一个字符串,问是否存在一个前缀和后缀相等,如果存在求最长的这样的前后缀。

思路:子串是否相等问题,典型的 hash 题。

最简单的思路是先求出所有前缀的 hash 值,储存在 map 中。
然后求出所有的后缀,判断是否有答案。
复杂度:n*log(n)

这道题数据范围只有 10^5,但是使用 n*log(n) 的复杂度会超时,所以有两个注意事项。

1、使用 unordered_map,不要使用 map。
2、从大往小遍历,找到一个就是最大答案马上结束。

当然,实际上我们不使用储存也可以做这道题,同时计算前后缀的 hash 值,比较即可。

五、最后

这次的比赛代码量比较大,又是筛素数,又是模拟题,我花费了不少时间才做完。

后头看看,模拟题面试题中可能会遇到,属于很常见的路径题,当然不会这么复杂。
而最后一题字符串题,面试中实际上很少遇到,遇到了大部分人也不会做,毕竟这些算法比较小众,听说过的不多。

最后再提醒下,网格上的路径题,需要使用大量 if/else 的时候,可以考虑是否可以使用我的这个方法。
这个方法可以使得代码变得非常清晰与简单,还不容易遗漏某种分支。

问答题:第三题和第四题,你以前使用过这种方法吗?

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越