vlambda博客
学习文章列表

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




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


题意


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

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

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


样例

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL


出题人的阴谋


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

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

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

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

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

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

那么阴我们的“怪物”在哪呢?就藏在我们思维的盲区处,在这题当中,我们思维的盲区就是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 = next
class 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 = next
class 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成功逆袭夺冠的。

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

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