题目链接：https://leetcode.cn/problems/rank-from-stream-lcci/

解题思路

这道题目的官方提示是使用一个携带额外信息的二叉搜索树来解决问题，用二叉搜索树的优点是对于输入数据的范围没有限制，但是缺点在于：如果使用朴素的二叉搜索树，最坏时间复杂度会很差，而平衡二叉搜索树的实现会比较复杂。考虑到题目中x的范围是[0, 5e4]，我们也可以使用树状数组来解决问题。

树状数组

树状数组（Binary Indexed Tree），也叫Fenwick Tree，是一种数据结构，可以用来高效地维护一个固定长度数组（设长度为N）的区间和。它支持两种操作：

题目网址：https://leetcode.cn/problems/multi-search-lcci/

解题思路

这题是前缀树（也叫字典树、Trie）的一个典型应用。我们可以将所有需要查询的单词插入到前缀树中，然后对字符串的每个字符进行遍历，查找以该字符为起点的所有单词。

参考实现

class Node:
    def __init__(self, idx=-1, children=None):
        self.idx = idx
        self.children = {} if children is None else children

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        # 构建前缀树
        root = Node()
        for i, s in enumerate(smalls):
            node = root
            for j, ch in enumerate(s):
                if ch not in node.children:
                    node.children[ch] = Node()
                node = node.children[ch]
                if j == len(s) - 1:
                    node.idx = i

        # 遍历大字符串，查找所有小字符串
        ans = [[] for _ in range(len(smalls))]
        for i in range(len(big)):
            node = root
            j = i
            while j < len(big) and big[j] in node.children:
                node = node.children[big[j]]
                j += 1
                if node.idx != -1:
                    ans[node.idx].append(i)
        return ans

题目链接：https://leetcode.cn/problems/get-kth-magic-number-lcci/

解题思路

这道题有时间复杂度为O(k)的解法，但是这里介绍一个更通用且更容易理解的算法，其时间复杂度为O(k log k)。

给出集合，其中。我们需要找到这个集合中的第k个最小值。注意到是单调递增的，也就是说如果，，，那么。因此，假如我们把这个问题看作一个按照大小顺序进行搜索的问题，那么下一个要搜索的(a, b, c)一定会和已搜索过的(a, b, c)相邻，所以我们只需要用一个优先队列来存储已搜索过的(a, b, c)的邻居，从中获取下一个要搜索的(a, b, c)即可。我们还需要一个哈希表来记录已搜索过的(a, b, c)，以避免重复搜索。

题目链接：https://leetcode.cn/problems/find-longest-subarray-lcci/

解题思路

这道题可以转化为一个经典的问题：在一个数组中找到和为k的最长子数组。我们只要将数组中的字母替换成1，数字替换成-1，那么原题就变成了在一个数组中找到和为0的最长子数组。

要解决这个问题，我们需要用到一个叫做“前缀和”的技巧。我们用sum(i, j)表示数组在区间[i, j)上的和（sum(i, i) = 0），如果令数组prefix[i] = sum(0, i)，那么就可以快速计算出sum(i, j) = prefix[j] - prefix[i]。

题目链接：https://leetcode.cn/problems/shortest-supersequence-lcci/

解题思路

这个题目属于一类很典型的问题：给定一个数组，要找到满足某个性质的最短子数组。这类问题往往可以用滑动窗口的方式来解决。

下面是滑动窗口的模板代码：

arr = get_input_arr()
status = init_status()
left = 0
right = 0
min_len = float('inf')
ans = []
while True:
    if right < len(arr) and not is_condition_met(status):
        right += 1
        status.update(left, right)
    else:
        if left == len(arr):
            break
        # 如果有多个相同长度的最短子数组，会保留左侧索引最小的
        if is_condition_met(status) and right - left < min_len:
            min_len = right - left
            ans = [left, right - 1]
        left += 1
        status.update(left, right)
return ans

原题网址：https://leetcode.com/problems/lru-cache/description/

实现思路

很显然，一个LRU缓存需要支持以下操作：

1. 将尾部的元素删除。（即淘汰最久未使用的元素）
2. 将其中一个元素移动到头部。（即将最近使用的元素标记为最新）
3. 将一个新元素插入到头部。
4. 给定key，查询对应的元素位置。

双向链表能够高效地实现操作1-3，而hash表能够高效地实现操作4，所以我们考虑同时使用双向链表和hash表来实现LRU缓存。

原题网址：https://leetcode.cn/problems/linked-list-cycle-lcci/

解题思路

这道题目就是经典的Floyd龟兔赛跑算法。这个算法主要分为两个部分，第一个部分就是如何判定是否有环，第二个部分就是如何找到环的起点。第一个部分比较简单，很容易理解，因此也很脍炙人口。但是第二个部分就比较少人知道了，因为其推导过程相对复杂一些，具体可以参考LeetCode官方的题解。