王争《数据结构与算法之美》课程笔记

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行数据淘汰。

我们建立一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

• 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
• 如果此数据没有在缓存链表中，又可以分为两种情况：
  • 如果此时缓存未满，则将此结点直接插入到链表的头部；
  • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
• 此时，缓存访问时间复杂度O(n)，可通过引入Hash表记录每个数据的位置将其降到O(1)

# Definition for singly-linked list.
class DbListNode(object):
    def __init__(self, x, y):
        self.key = x
        self.val = y
        self.next = None
        self.prev = None


class LRUCache:
    '''
    leet code: 146
        运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。
        它应该支持以下操作： 获取数据 get 和 写入数据 put 。
        获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
        写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。
            当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间
    哈希表+双向链表
    哈希表: 查询 O(1)
    双向链表: 有序, 增删操作 O(1)
    Author: Ben
    '''

    def __init__(self, capacity: int):
        self.cap = capacity
        self.hkeys = {}
        # self.top和self.tail作为哨兵节点, 避免越界
        self.top = DbListNode(None, -1)
        self.tail = DbListNode(None, -1)
        self.top.next = self.tail
        self.tail.prev = self.top
    
    def get(self, key: int) -> int:
    
        if key in self.hkeys.keys():
            # 更新结点顺序
            cur = self.hkeys[key]
            # 跳出原位置
            cur.next.prev = cur.prev
            cur.prev.next = cur.next
            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur
    
            return self.hkeys[key].val
        return -1
    
    def put(self, key: int, value: int) -> None:
        if key in self.hkeys.keys():
            cur = self.hkeys[key]
            cur.val = value
            # 跳出原位置
            cur.prev.next = cur.next
            cur.next.prev = cur.prev
    
            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur
        else:
            # 增加新结点至首部
            cur = DbListNode(key, value)
            self.hkeys[key] = cur
            # 最近用过的置于链表首部
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur
            if len(self.hkeys.keys()) > self.cap:
                self.hkeys.pop(self.tail.prev.key)
                # 去掉原尾结点
                self.tail.prev.prev.next = self.tail
                self.tail.prev = self.tail.prev.prev
    
    def __repr__(self):
        vals = []
        p = self.top.next
        while p.next:
            vals.append(str(p.val))
            p = p.next
        return '->'.join(vals)

if __name__ == '__main__':
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache)
    cache.get(1)  # 返回  1
    cache.put(3, 3)  # 该操作会使得密钥 2 作废
    print(cache)
    cache.get(2)  # 返回 -1 (未找到)
    cache.put(4, 4)  # 该操作会使得密钥 1 作废
    print(cache)
    cache.get(1)  # 返回 -1 (未找到)
    cache.get(3)  # 返回  3
    print(cache)
    cache.get(4)  # 返回  4
    print(cache)

什么是链表

和数组一样，链表也是线性表的一种。但不同于数组需要一块连续的内存空间来存储数据，链表它通过指针将一组零散的内存块串联起来使用。

• 内存块称为链表的结点（Node），每个结点存储数据，并记录下一个结点的地址。

链表的特点

• 数组在进行插入、删除操作时，为了保证内存的连续性，需进行数据搬移；而链表存储空间本身就是不连续的，因此插入或删除操作非常方便，只需要更改指针指向即可。复杂度O(1)

  

• 链表随机访问元素比较困难，需要根据指针一个结点一个结点的进行遍历，直到直到相应的结点；无法再像数组那样根据首地址和下标通过寻址公式直接计算出对应内存地址了。复杂度O(n)

常见的链表结构

（1）单链表

• 第一个结点称为头结点，记录链表的基地址
• 最后一个结点称为尾结点，尾结点不会指向下一个结点，而是指向一个空地址NULL

（2）循环链表

• 首尾相连，从链尾到链头比较方便，适合解决具有环形结构的数据处理问题，比如约瑟夫问题

（3）双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表支持两个方向，每个结点不止有一个后继指针 next指向后面的结点，还有一个前驱指针prev指向前面的结点

相比于单向链表，占用更多的存储的存储空间，但前驱结点的存在也直接导致了双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

• 给定data删除对应结点时，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过改变指针方向将其删除(复杂度O(1))。总复杂度O(n)
• 给定地址删除对应结点时，需先获得该结点 q的前驱结点，单链表需要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q的前驱结点，复杂度O(n)。但是双向链表中的结点已经保存了前驱结点的指针prew，不需要像单链表那样遍历，直接删即可，复杂度O(1)

对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

用空间换时间的设计思想：当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。

（4）双向循环链表

• 首节点的prew指针指向尾节点的data，尾节点的next指针指向首节点的data

链表VS数组

• 数组因连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高；而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读，访问效率较低。
• 数组大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它时，会导致“内存不足（out of memory）”；如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，复制原数组数据非常耗时。链表本身没有大小的限制，天然地支持动态扩容

习题

如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？相应的时间空间复杂度又是多少呢

基本思路

• 通过快慢指针法确定链表中心点（快指针一次两格，慢指针一次一格，等快指针到达尾部时，慢指针恰好到达中心点处）
• 将链表后半段反序
• 一个指针在头部，一个在中心点，开始逐个比较。

时间复杂度为O(n)，空间复杂度O(1)

未完待续…