数据结构设计 - 《LeetCode Notebook》

146. LRU Cache

需要注意的地方：任意BiListNode实例不仅存在于双向链表中，还存在于**LRUcache**中，添加和删除的时候必须同步进行。

class BiListNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None
class LRUCache:
    def __init__(self, capacity: int):
        self.LRU = dict()              # 存放key:BiListNode(key,value)的字典
        self.capacity = capacity
        self.size = 0
        self.head = BiListNode()       # 避免空判断，伪头尾节点
        self.tail = BiListNode()
        self.head.next = self.tail     # 靠近头部的为最近使用(get, put)的节点，反之亦然
        self.tail.prev = self.head
    def get(self, key: int) -> int:
        if key not in self.LRU:
            return -1
        node = self.LRU[key]
        self.delete_node(node)
        self.add_to_head(node)
        return node.value
    def put(self, key: int, value: int) -> None:
        if key in self.LRU:
            node = self.LRU[key]
            node.value = value                   # 存储的是节点，会一并更改
            self.delete_node(node)
            self.add_to_head(node)
        else:
            node = BiListNode(key, value)
            self.LRU[key] = node                 # 不要忘记加入LRU缓存！
            self.add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                tail_node = self.tail.prev
                self.delete_node(tail_node)
                self.LRU.pop(tail_node.key)      # 不要忘记删除LRU缓存！
                self.size -= 1
    def delete_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    def add_to_head(self, node):
        node.next, node.prev = self.head.next, self.head
        self.head.next = node
        node.next.prev = node

时间复杂度：get和put均为
空间复杂度：

208. Implement Trie (Prefix Tree)

Approach I** 建立TrieNode节点
每个TrieNode节点拥有一个children数组，指向26**个字母，is_end则代表是否为单词尾部。

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            index = ord(ch) - ord('a')
            if not node.children[index]:
                node.children[index] = TrieNode()
            node = node.children[index]
        node.is_end = True
    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            index = ord(ch) - ord('a')
            if not node.children[index]:
                return False
            node = node.children[index]
        return node.is_end
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            index = ord(ch) - ord('a')
            if not node.children[index]:
                return False
            node = node.children[index]
        return True

时间复杂度：初始化，每次查询或插入为，是字符串或前缀的长度
空间复杂度：，是字符串长度之和，是字符集大小（26）

Approach II** 直接使用字典**

class Trie:
    def __init__(self):
        self.lookup = {}      # 查询字典（树的根节点）
    def insert(self, word: str) -> None:
        node = self.lookup
        for ch in word:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node['#'] = '#'       # 单词尾部标记
    def search(self, word: str) -> bool:
        node = self.lookup
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return True if '#' in node else False
    def startsWith(self, prefix: str) -> bool:
        node = self.lookup
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True

440. K-th Smallest in Lexicographical Order

**字典树**应用题。
数据结构设计 - 图9
核心：按照字典序的定义，以i开头的所有数字必定位于以i+1开头的所有数字前面。

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count(cur) -> int:
            """
            返回以cur开头的（包括）且 ≤n 的数字数量
            """
            cnt = 0
            low, high = cur, cur
            while low <= n:
                cnt += min(high, n) - low + 1
                low *= 10
                high = 10 * high + 9
            return cnt
        cur = 1
        k -= 1
        while k:
            if (cnt := count(cur)) <= k:
                k -= cnt
                cur += 1
            else:
                k -= 1
                cur *= 10
        return cur

时间复杂度：
空间复杂度：

295. Find Median from Data Stream

使用大根堆与小根堆（Python默认）来实现。对于大根堆，add和get都需要取反。

class MedianFinder:
    def __init__(self):
        self.A = []        # 小根堆（优先存储，较大数）
        self.B = []        # 大根堆（较小数）
        self.N = 0         # 已存储的数字个数
    def addNum(self, num: int) -> None:
        if self.N & 1:
            heapq.heappush(self.B, -heapq.heappushpop(self.A, num))
        else:
            heapq.heappush(self.A, -heapq.heappushpop(self.B, -num))
        self.N += 1
    def findMedian(self) -> float:
        return self.A[0] if self.N & 1 else (self.A[0] - self.B[0]) / 2.0

时间复杂度：find操作是，add操作（堆的插入与弹出）是
空间复杂度：

Follow up

If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

如果数据流中所有整数都在 0~100 范围内，那么我们可以利用计数排序统计每一类数的数量，并使用双指针维护中位数。

If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

如果数据流中 99% 的整数都在 0~100 范围内，那么我们依然利用计数排序统计每一类数的数量，并使用双指针维护中位数。对于超出范围的数，我们可以单独进行处理，建立两个数组，分别记录小于 0 的部分的数的数量和大于 100 的部分的数的数量即可。当小部分时间，中位数不落在区间 [0,100] 中时，我们在对应的数组中暴力检查即可。