爆资讯爆资讯爆资讯

不仅游戏里会坑人,来看看LeetCode出题人是怎么埋坑的

今天是LeetCode专题的第35篇文章,上一篇文章当中我们一口气肝了三题,不知道大家感觉怎么样?我们来放松一下,看一道相对比较简单也比较有趣的问题。

题意

这题的题意也只有一句话,秉承了LeetCode一贯题狠话不多的风格。

题意是给定一个链表和一个整数K,要求将链表当中的所有元素向右移动K位。

注意这里,元素往右边移动的意思并不是删除了,移动出边界的元素会放置到最左边。

样例
Input: 1->2->3->4->5->NULL, k = 2Output: 4->5->1->2->3->NULLExplanation:rotate 1 steps to the right: 5->1->2->3->4->NULLrotate 2 steps to the right: 4->5->1->2->3->NULL
Input: 0->1->2->NULL, k = 4Output: 2->0->1->NULLExplanation:rotate 1 steps to the right: 2->0->1->NULLrotate 2 steps to the right: 1->2->0->NULLrotate 3 steps to the right: 0->1->2->NULLrotate 4 steps to the right: 2->0->1->NULL
出题人的阴谋

在我们正式开始做题之前,先来说点题外话。如果大家玩过一些著名的硬核动作游戏,比如黑魂、只狼、仁王等等,会发现这些游戏当中都有一个惯用的套路,就是墙角怪。

我没找到合适的游戏截图,就来自己手动画一张。

不仅游戏里会坑人,来看看LeetCode出题人是怎么埋坑的

这个套路其实并不高明,说白了就是在显眼的地方放一个宝物,玩家瞥一眼就会看到。但是在玩家视野的盲区会藏一个怪物,如果玩家贸贸然去捡这个宝物,那么怪物就会冲上来给玩家致命一击,把玩家阴死。

这其实利用的人们的直线思维,也就是本能反应。

当你明白了这个道理之后,你会发现不仅仅是游戏,很多问题就是利用人们的直线思维来困住我们。比如这题,也藏着一个出题人故意挖的坑。

我们来仔细看一下,这题的题意非常明显,我们一眼看完就能想到解法。其实这个就相当于游戏中的宝物,玩家看到宝物的第一反应就是去捡,同样,我们想出解法之后的第一反应就是去编码。那么这样直线思维的结果就是被阴。

那么阴我们的“怪物”在哪呢?就藏在我们思维的盲区处,在这题当中,我们思维的盲区就是K。我们就觉得这是一个普通的整数就放过了,往往不会多想。就好像游戏里的墙角,我们本能地觉得墙角后面没有东西一样。但其实出题人并没有给出K的范围,这个K可能会很大,大到我们无法在规定的时间内遍历完。

所以如果我们贸贸然上去用模拟的方法一个一个地移动链表的话,结果就是被阴,测试的时候样例全都通过,但是一提交就TLE(time limited exceed),也就是超时。

如果你做多了题目,可能会很容易发现这个坑,但是还有另外一个坑等着你。这个坑相比之下更加阴险,也就是说出题人其实在墙角藏了两只怪,K只是其中比较明显的那只。那么另外一只怪是什么呢?

另外一只怪就是我们的这个链表了,有谁规定了这个链表一定是有元素的?如果链表本身就是空的怎么办?

这个时候你用K对n取模就会报错,因为n不能为0。在LeetCode当中还好,我们提交一次看到报错的数据也就知道了。但如果是线上的算法比赛,很有可能会坑掉你很多时间去debug。虽然我饱经锻炼,但是有时候不小心还是会踩坑。

所以我们做题的时候需要冷静下来思考一下,尤其要小心变量的范围,往往当中藏着巨坑。

题解

其实这题识破了这个坑之后就基本上没有难度了,解决K范围的方法也很简单。对于长度为n的链表而言,如果它这样移动n次相当于回到原点。那么我们直接用K对n取模,得出的余数才是我们真正需要移动的距离。

我们可以开辟一个数组,先把链表中的元素全部另外存储一遍,自己重新构造新的链表进行返回,也可以模拟链表的移动过程,在原链表上操作。这两种方法都是可以的,我们一种一种来看代码。

我们先来看第一种做法的代码:

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def rotateRight(self, head: ListNode, k: int) -> ListNode:        pnt = head        elements = []        # 直接遍历链表,把元素全部存在list中        while pnt is not None:            elements.append(pnt.val)            pnt = pnt.next                    n = len(elements)        if n == 0:            return pnt                k %= n        # 通过切片,我们可以很方便地实现移动操作        elements = elements[n-k:] + elements[:n-k]                head = ListNode()        pnt = head                 # 重新构建链表返回即可        for e in elements:            cur = ListNode(e)            pnt.next = cur            pnt = cur        return head.next

如果操作链表的话速度会快很多,因为我们节省了开辟内存以及切片元素的开销。但是相比于上面这种写法会复杂一些,因为我们移动链表本质上是将链表切分成了两个部分,然后再调换顺序拼接到一起。

但是这里有一个坑,如果k=0的时候,链表是切分不出来两个部分的,所以对于这种情况需要单独判断。好在k=0的时候也简单,k=0说明不需要移动,那么我们直接返回即可。

由于链表操作非常琐碎,所以整个代码可读性不佳,这也是很多大神讨厌使用链表的原因。我们来看下代码:

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def rotateRight(self, head: ListNode, k: int) -> ListNode:        pnt = head        n = 0        # 计算链表长度        while pnt is not None:            n += 1            pnt = pnt.next                    if n == 0:            return pnt                k %= n        if k == 0:            return head                pnt = head        # 链表向右移动k个元素,其实是把倒数k个元素放到头部        # 也就是说头部的元素是n-k个        for i in range(n-k-1):            pnt = pnt.next                cur = pnt.next        pnt.next = None                pnt = cur                # 将末尾的元素接到头部        while pnt.next is not None:            pnt = pnt.next                    pnt.next = head        return cur
结尾与升华

到这里,这道题就算是完整讲完了。

很多人觉得算法题很难,acm更难,这些算法比赛难除了算法本身的困难之外,还有很大的一部分原因就在这里了。出题人在题目当中埋坑设置trick是非常普遍的做法,像是著名的codeforces和topcoder比赛甚至开创了互相hack的机制。

也就是让选手们互相阅读对方的代码,发现对方中招的话,就构造数据去hack掉对方的解答。一旦hack成功就能获得大量的分数奖励,所以高阶选手除了能够享受比赛本身的乐趣之外,还可以体验一把竞技游戏的感觉。据说楼教主有一次就是因为比赛结束之前,接连hack成功逆袭夺冠的。

和一些硬核游戏一样,算法做题本身的正反馈其实是很足的。只是前期的门槛比较高,很多人迈不过去。这时候除了多做多练提升自己的水平之外,也要学会摸清楚出题人的套路,既可以增加成功率,也会找到新的乐趣。

今天的文章就到这里,原创不易,关注我,获取更多精彩文章。

未经允许不得转载:爆资讯 » 不仅游戏里会坑人,来看看LeetCode出题人是怎么埋坑的

相关推荐