查看原文
其他

Python 没有指针,如何解算法题?

Python猫 2021-03-15

The following article is from 未闻Code Author kingname

👆 Python猫” ,一个值得加星标的公众号

花下猫语:今天一大早,读者群里又讨论了 Python 的“指针”问题。之前在公众号里发布过樱雨楼小姐姐的《对比 C++ 和 Python,谈谈指针与引用》,它从概念上有比较清晰的分析。恰好今天还看到青南同学刚发布的一篇文章,它从实用的层面介绍了怎么用 Python 解“指针”类的题目,正好分享一下~

剧照 | 《如懿传》

原标题:《举一反三:三种问题,两个指针,一种方法》

在我们做算法题的时候,如果大家多总结解题方法,就会发现很多题目的解题方法实际上是完全一样的。今天我们就来看三道链表相关的题目。可以使用同一种方法来解决。

虽然题目中用到了指针,但我们知道,Python 是没有指针的,所以在 Python 里面,这里实际上指的是引用。不过由于“指针”这个词更加形象,所以下文我们还是会用指针来表示对一个对象的应用。

先来看我们将要解决的三道题目:

题目1:只扫描一次链表,O(1)空间复杂度,返回链表倒数第 k 个节点。

题目2:只扫描一次链表,O(1)空间复杂度,返回链表中间的节点。

题目3:空间复杂度(1),查询链表是否有环。

其中前两道题要求只能扫描链表一次。但是大家可能会有疑问,例如对于第2题,都不知道链表一共有多少个节点,怎么可能知道中间的节点是哪个?但如果提前把链表扫描一遍,知道一共有多少个节点了,又不能再次扫描链表,那么就必须把每个节点和序号都存下来,这样空间复杂度就不可能是 O(1)了。

我们先来看看第2题,找到链表中间的节点。

从下图的两个链表可以看到:

链表有 n 个节点,如果 n 为奇数,那么中间的节点在第 (n + 1) / 2个节点。如果 n 为偶数,那么中间的节点在第n / 2个节点。

这个信息怎么使用呢?我们看下面一个表格:

既然如此,如果我们在链表里面有两个指针(引用),其中一个每次移动2个节点,另一个每次移动一个节点。这样当快的指针移动到了末尾,慢的指针刚刚好指向中间的节点。

用代码来表示:

def find_mid(node):
    if not node:
        return None
    if not node.next:
        return node
    fast = slow = node
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow

返回的 slow 就是最中间的节点。

再来看第3道题。跟第二题一样,也是一快一慢两个指针,如果链表有环,那么快的指针会绕到慢的指针的后面,然后追上来。只要看快的指针是否跟慢的指针重合,就知道是否有环了:

def find_cycle(node):
    if not node:
        return False

    slow = fast = node
    while fast:
        fast = fast.next
        if not fast:  # 快的指针到了链表末尾,说明没有环
            return False
        if fast is slow:  # 快的指针追上了慢的指针,说明有环
            return True
         fast = fast.next
         if fast is slow:
            return True
         slow = slow.next
    return False

再来看第一题。跟第二题实际上也是一样的。只不过,这次两个指针是移动速度是一样的。但是,一种一个指针先移动 k 个节点,然后两个指针再开始同时移动。这样两个指针中间始终会间隔 k 个节点。这样一来,当先走的指针到了None,后走的指针刚刚好走到倒数第 k 个节点。

不过,在解决这道题的时候,需要考虑,k 如果大于链表长度的时候,应该要返回错误信息。对应的代码如下:

def find_reverse_k(node, k):
    if not node or k == 0:
        return None
    front = behind = node
    window = 0
    while front:
        window += 1
        front = front.next
        if window == k:
            break
    else:  # while ... else 语法,如果循环正常结束,就会进入 else
        raise Exception('k 比链表长度还长!')
    while front:
        front = front.next
        behind = behind.next
    return behind

如果大家观察上面三个问题的解决代码,会发现他们都是使用了两个指针,通过两个指针之间的节点差来解决问题的。

优质文章,推荐阅读:

Python 为什么用 # 号作注释符?

Python 编程语言的核心是什么?

为什么Python不用设计模式?

Python 内存分配时的小秘密

感谢创作者的好文

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存