一周LeetCode习题精选

LeetCode 208

本题要求构造一个前缀树。前缀树是数据结构中树的一种，用于检索字符串数据集中的值，在自动完成、拼写检查、IP路由等方面都有应用。前缀树节点有两个字段：一个链接到字符串的下一个字符节点child，另一个为布尔值is_end，判断指定节点是否已到末尾。这里需要说一下Python的collections.defaultdict()这个方法，此方法构建了一个类似字典的对象，与普通字典不同的是，在查找字典中不存在key时，普通字典会报错，而defaultdict不会返回错误，而是返回一个默认值。本例会返回一个TrieNode节点，这样省去了在功能方法中新建节点的步骤。本题要求实现三个前缀树的三个功能：插入单词、搜索给定单词是否存在于前缀树以及搜索给定单词是否是前缀树中单词的前缀。

    class TrieNode:
        def __init__(self):
            self.child = collections.defaultdict(TrieNode)
            self.is_end = False

    class Trie(object):
        def __init__(self):
            self.root = TrieNode()

对于插入单词功能，需要从前缀树的根节点开始，遍历单词的每个字母，依次添加。例如，当前的字母为“e”，则直接转到key为“e”的节点，上文已经说过，如果查找不到节点，则会返回新节点。遍历完成后，将is_end值设为True。

    def insert(self, word):
        cur = self.root
        for w in word:
            cur = cur.child[w]
        cur.is_end = True

对应搜索单词功能，还是从根节点开始遍历，此时使用defaultdict的get方法取值，如果取到的值为空，说明到此为止已经匹配不到了，会出现两种情况，如果单词还剩余字母未匹配，那么搜索失败。如果单词匹配完毕，is_end值为True时，表示匹配成功，is_end值为False，表示仅匹配了前缀树中单词的前缀，搜索仍失败。

    def search(self, word):
        cur = self.root
        for w in word:
            cur = cur.child.get(w)
            if cur is None:
                return False
        return cur.is_end

对应搜索单词前缀功能，与搜索完整单词的方法一致，因为前缀比完整单词要短，所以如果get方法取到的值为空，意味者匹配失败，其他情况均匹配成功。

    def startsWith(self, prefix):
        cur = self.root
        for w in prefix:
            cur = cur.child.get(w)
            if cur is None:
                return False
        return True

LeetCode 287

链接：Find the Duplicate Number 找出数组中的重复数字。这道题可用多种方法解决，这里介绍两种方法。第一种是使用排序，数组排序后，重复数字一定是排在一起的，只要检测相邻数字是否重复即可，代码也比较简单。

    class Solution:
        def findDuplicate(self, nums):
            nums.sort()
            for i in range(1, len(nums)):
                if nums[i] == nums[i-1]:
                    return nums[i]

第二种方法是龟兔赛跑算法，也称为弗洛伊德判圈算法，这个算法原本用来检测单链表是否有环，这里是此用法的一个变型。使用兔子和乌龟两个值，开始时均在数组头。乌龟一次向后移动一步，兔子一次向后移动两步。若存在环，则兔子和乌龟必能相遇。在本题，兔子和乌龟走的步数要跟据数组的值来定，比如nums[0]=1，nums[1]=4，乌龟要在索引0要走到索引1，而兔子在索引0要先走到索引1，索引1的值为4，所以要再走到索引4。因为兔子和乌龟走的都是索引，所以可能出现兔子和乌龟最终在同一个索引相遇的情况，而数组中重复的值索引不同，这样就需要第二次循环。

    class Solution:
        def findDuplicate(self, nums):
            tortoise = nums[0]
            hare = nums[0]
            while True:
                tortoise = nums[tortoise]
                hare = nums[nums[hare]]
                if tortoise == hare:
                    break

            ptr1 = nums[0]
            ptr2 = tortoise
            while ptr1 != ptr2:
                ptr1 = nums[ptr1]
                ptr2 = nums[ptr2]
            return ptr1

参考资料： Python中defaultdict的用法详解 LeetCode 208题解 Floyd判圈算法 LeetCode 287题解

LeetCode 208#

LeetCode 287#

LeetCode 208

LeetCode 287