ARTS-Week 2

每周至少写一道算法题，阅读并点评至少一篇英文文章，学习至少一个技术技巧，分享一篇有观点和思考的技术文章。这周主要学习链表相关的知识，并且 AC 了 leetcode 的几道链表相关的题目，包括环形链表的判断、链表合并以及删除结点，分享python的一个翻译库，以及spark文档。

Algorithm

做一些链表相关的题目。

环形链表

141. Linked List Cycle

给定头结点，判断是否是环形链表（链表中是否有环）。

哈希表

首先想到的是循环遍历一遍，保存循环过程中的结点，之后在每次遍历的时候都先判断是否已经存在该结点，如果存在该结点，也就说明该结点之前出现过，也就是该链表是环形，否则就一直遍历下去，直到循环结束。

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        node_set = set()
        node = head
        while node is not None:
            if node in node_set:
                return True
            node_set.add(node)
            node = node.next
        return False

不过这种方法会增加额外的内存空间，最大空间复杂度为 O(2n)，并且在每次判断是否存在的时候也会耗费一些时间。

快慢指针

设置两个指针，一个 slow 指针每次只前进一格，fast 指针每次前进两格，如果链表有循环，就一定会在某个点相遇，否则就直接运行到链表结尾，只要判断 slow 指针和 fast 指针是否相等就能判断是否存在环形。

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

这种方法算是最优解了，不会增加额外的空间，只用了两个指针，空间复杂度为 O(1) ，时间复杂度也只是遍历一遍的时间，为 O(n) 级别，在循环的时候需要注意边界条件的判断，注意是否为空，而且不用注意 slow 是不是空，只要关心 fast 就行。

当然，上面两种都是常规做法，不会影响到原来链表的数据，我在写完之后看别人的代码的时候发现了个投机的写法，就是改变链表中的数据，做一个 flag 的作用，每次循环只要判断是否存在 flag 就能判断是否出现了环，否则直接运行到结尾返回 False 。

设置 Flag

是基于哈希表的原理来的，哈希表因为会增加额外的空间，最主要的目的还是判断是否出现过，同样是判断是否出现过，还可以以设置 flag 标志的方式来判断。

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        while head and head.val is not None:
            head.val = None
            head = head.next
        if head is None:
            return False
        return True

不过这种方法会修改原来的链表，而且还不确定原链表中是否真的有这个标识，不过就目前的题目来看，这个方案是 AC 的。

142. Linked List Cycle II

这题目是上一题的变体，上一题只是要求判断是否是循环链表（环），而这一题不仅要判断是否是环形链表，还要找到环形链表的入口结点，也就是尾部结点所指向的下一个结点。

哈希表

使用这个方式与上一题基本一样的解法，就把返回值修改为返回结点就行了。

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        node_set = set()
        node = head
        while node is not None:
            if node in node_set:
                return node
            node_set.add(node)
            node = node.next
        return None

简单暴力，牺牲空间。

快慢指针

这一题依旧可以使用这种方式来解决，不过需要注意，如果存在循环的情况下，两者相遇的结点不一定是环的入口结点，他们可能会出现在那个环中的任何一处位置，这时候需要另外处理。

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        if fast is None or fast.next is None:
            return None

        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return slow

前面的部分还是一样，两个指针不同速度，求出是否是环形链表，如果为 None 就返回 None 表示不是环形，如果判断是环形的话，此时 slow 和 fast 指针指向的是同一个结点。

这个时候需要一些推倒：

假设 F 表示指针 fast 走过的距离，S 表示指针 slow 走过的距离，相遇点为 C ，环的方向为顺时针，环的周长为 b 。

此时，因为 fast 指针每次前进两格，slow 指针每次前进一格，所以有 F = 2*S ，而 F 的距离可以表示为 F = AB + nb + BC ，fast 指针可能经过了 n 圈再加上 AB 和 BC 的距离，slow 指针的距离为 AB + BC ，则 2(AB+BC) = AB + nb + BC ，而 CB = b – BC，环的另一半距离，则有 AB = (n-1)b + CB ，也就是 AB 的距离为转了很多个圈的距离加上环的另一半 CB 的距离，当一个结点在链表的开始结点 A 的时候，另外一个链表在 C 的时候，两者每次前进一格，可能 C 点的指针会在环内转（n-1）个圈，假设已经到了最后一圈了，公式中的 n=1 了，所以所对应的就是 AB = CB ，两个结点再继续走相同的距离，就会在 B 点相遇，也就是环的入口结点。

所以，对应的函数的后半部分就是将其中一个指针放到头结点，两个指针每次前进一格，最后两者相等的点就是环的入口结点了。

合并链表

21. Merge Two Sorted Lists

总的思路就是桶排序，每次都比较头结点的值，拿出比较小的一项，添加进新的排序链表中，之后指向下一项，一直到链表结尾。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        ans = ListNode(None)
        pev = ans
        while l1 and l2:
            if l1.val < l2.val:
                pev.next = ListNode(l1.val)
                l1 = l1.next
            else:
                pev.next = ListNode(l2.val)
                l2 = l2.next
            pev = pev.next
        pev.next = l1 if l1 else l2
        return ans.next

首先，建立一个带头指针（ans），指向哨兵结点 pev，判断 l1 和 l2 是否存在，不为空，之后循环，判断这两个结点的值，取出比较小的那个，将对应的链表向后移动一格，同时哨兵结点创建对应值的结点，在每次循环之后，哨兵点向后移一格，最后只要有任何一个链表（l1、l2）为空的之后，将 pev 指针指向不为空的那个链表，最后返回带头结点的下一个结点就是正确答案。

简单来说就是有个带头结点保存新的链表，而哨兵结点就是在这个新链表上依据需求创建新的结点，最后获得一个新的链表。

当然，这题也可以用递归的方式来写，不过这种方式就很占用递归空间。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 递归
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

首先判断是否为 None ，之后依据两个链表的大小，返回链表中较小的那个结点和后面剩余元素递归合并的结果。

删除结点

19. Remove Nth Node From End of List

删除倒数的第n个结点。

首先想到的是求出整个链表的长度，之后在计算出倒数第n个结点的位置，重头遍历，删除该结点。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        pev_head = ListNode(None)
        pev_head.next = head
        l = 0
        pev = head
        while pev:
            l += 1
            pev = pev.next
        l -= n
        pev = pev_head
        while l:
            l -= 1
            pev = pev.next
        pev.next = pev.next.next
        return pev_head.next

pev_head 作为带头结点，指向头部结点 head， 因为有可能的情况就是需要删除第一个结点，这个时候需要有指针指向它才能删除，之后循环，计算整个链表的长度 l ，因为需要求出删除倒数第 n 个结点，所以 l = l – n 求出正序的结点位置，重新从带头结点开始遍历，循环到需要删除的结点的前一个结点（因为增加多一个带头结点关系），修改指针的指向，达到删除的目的，最后返回带头结点的下一个结点，这个时候不能返回 head ，有可能 head 结点已经被删除了。

这个方法的时间复杂度比较大，为 O(L) ，还有一种方式是使用两个指针。

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        pev_head = ListNode(None)
        pev_head.next = head
        first_node = pev_head
        second_node = pev_head
        while n:
            second_node = second_node.next
            n -= 1
        while second_node.next:
            first_node = first_node.next
            second_node = second_node.next
        first_node.next = first_node.next.next
        return pev_head.next

大概的思路就是设置两个指针，指向 head 结点的带头结点 pev_head （理由和前面一致），之后将其中一个结点 second_node 向后移动 n 格，之后将两个结点同时移动，知道移动到 second_node 结点的末尾，其实这个时候，这两个结点的距离就是 n ，当后面的结点到链表的末尾的时候（最后一个结点的位置而不是空），第一个结点 first_node 也就指向了倒数的第 n 个结点的前驱结点，之后删除 first_node 后面的结点，最后返回 pev_head 的下个结点。

Review

• What every computer science major should know

每个计算机学科的人都应该知道的事。

简要概括：

作者围绕四个方便，简述了计算机学科中各个方面的知识要求，简述了内容，并且提供了一些学习列表，还有针对的列出一些别的文章链接，方便学习查阅。

Tip

• 在线小工具集合

一个很不错的工具网站，提供了很多实用的工具。

在线工具集合，包括了很多使用的小工具，可以帮助快速解决一些事情，不过对于一些敏感信息不建议使用该工具，网站是非HTTPS的，对于一些重点关注的信息，例如身份证等信息还是不要在这里查了。

平时使用的一些加密解密，编码之类的可以在这里使用，也算很不错的一个工具集合。

对于一些热门的数据也有，并且接口比较暴露，可以直接使用，以垃圾分类的接口为例子,该接口就是直接暴露，没有什么验证措施，为此，为此，也可以使用这样的接口做一些东西。

F12 查看网络请求的状态会发现接口直接是一个get请求，没有任何的验证措施。

返回的数据可能是 ES 之后的数据：

{
    "5": {
        "name": "保健品瓶子",
        "type": "有害垃圾"
    },
    "68": {
        "name": "雷达瓶子",
        "type": "有害垃圾"
    },
    "147": {
        "name": "指甲油瓶子",
        "type": "有害垃圾"
    },
    "2225": {
        "name": "洁厕灵瓶子",
        "type": "可回收物"
    },
    "2326": {
        "name": "老干妈瓶子",
        "type": "可回收物"
    }
}

对于这样的数据就可以直接使用，或者封装新的接口来使用。

• Python 的翻译库

有时候要用到一些翻译的接口，不过只是进行一些简单的翻译工作，不需要多精确，并且也只是需要翻译一些简单的语言的时候，就可以使用这个库。这个库是谷歌提供的一个免费的翻译库，不需要注册，而且免费使用。

pip install googletrans

使用：

from googletrans import Translator
translator = Translator(service_urls=['translate.google.cn'])
translate = translator.translate("apple", src='en', dest='zh-cn')
print(translate.text)

需要注意，service_urls 需要修改成 translate.google.cn （谷歌翻译的中国域名）才能使用，不然会默认使用 translate.google.com 会访问失败。

参考：

• Googletrans: Free and Unlimited Google translate API for Python 官方文档
• 翻译服务

Share

• The Internals of Apache Spark 2.4.2

Apache Spark 的 Gitbook 文档。