0%

LeetCode题解146

发表于 更新于 分类于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

LeetCode题解

第146题 LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

原题如上，代码如下：

python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class new_node:
    def __init__(self,key=0,value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache(object):
    def add_none(self,node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    def remove_node(self,node):
        prev = node.prev
        new = node.next
        prev.next = new
        new.prev = prev
    def move_to_head(self,node):
        self.remove_node(node)
        self.add_none(node) 
    def remove_last_node(self):
        last = self.tail.prev
        self.remove_node(last)
        return last

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head = new_node()
        self.tail = new_node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        node = self.cache.get(key)
        if not node:
            return -1

        self.move_to_head(node)
        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        node = self.cache.get(key)
        if not node:
            newnode = new_node(key,value)
            self.cache[key] = newnode
            self.add_none(newnode)
            self.size += 1
            if self.size > self.capacity:
                tail = self.remove_last_node()
                del self.cache[tail.key]
                self.size -= 1
        else:
            node.value = value
            self.move_to_head(node)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

1k30Mj.png

解析：

首先，我们看到这个题所要构建的数据结构要求要在常数时间内完成get和put操作，那么可以用到哈希表，也就是python中的字典结构，辅助双向链表记录key-value信息，对于双向链表加入head和tail两个哨兵方便使用。

整体结构为：

1kc46s.png

我们先构造链表结构：

1
2
3
4
5
6
class new_node:
    def __init__(self,key=0,value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

对于字典结构key值是数据结构中的key，而字典中的value是链表中的结构体Node。

在我们构造LRUcache之前，我们先得构造几种方法，并结合要求使用。

首先，LRU是最近最久未使用，我们可以用双向链表进行对使用时间进行有序排序，即最近到最久的顺序。链表中最后一个，也就是最久没有使用的那一个。

对双向链表进行维护时，会有多种情况：

  1. put一个key相同的key-value，我们不用管它们的value是否相同，对我们而言是要原来的key-value进行更新，我们要将原来的key-value更新后将其位置移动到第一个。这时候无论cache是否满的，都不会溢出，因为只是更新处理而已。

  2. put一个新的key-value，我们会构建一个新的key-value结构体，并加入到链表中放到第一个位置，在字典中也加入新的key-value，然后判断是否溢出缓存，若溢出，那么将最久未使用也就是链表中最后一个元素删除，同时删除字典中该元素的key-value。

    上述中我们发现我们还需要：

    1. 在链表中新加Node并放置在第一个位置：

      1
      2
      3
      4
      5
      def add_none(self,node):
      	node.prev = self.head
         node.next = self.head.next
         self.head.next.prev = node
         self.head.next = node

    2. 移除old_Node：

      1
      2
      3
      4
      5
      def remove_node(self,node):
          prev = node.prev
          new = node.next
          prev.next = new
          new.prev = prev

    3. 将old_Node移动到第一个位置：

      1
      2
      3
      def move_to_head(self,node):
          self.remove_node(node)
          self.add_none(node)

    4. 将最后一个Node删除：

      1
      2
      3
      4
      def remove_last_node(self):
          last = self.tail.prev
          self.remove_node(last)
          return last

      返回Node是为了使用它在字典中将它删除。

  3. get一个key，查询其value，若没有，返回-1，若有，返回其value，并刷新使用时间，也就是将其key-value移动到链表第一个位置。

由上述就可以构造put和get方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def put(self, key, value):
    """
    :type key: int
    :type value: int
    :rtype: None
    """
    node = self.cache.get(key)
    if not node:
        newnode = new_node(key,value)
        self.cache[key] = newnode
        self.add_none(newnode)
        self.size += 1
        if self.size > self.capacity:
            tail = self.remove_last_node()
            del self.cache[tail.key]
            self.size -= 1
    else:
        node.value = value
        self.move_to_head(node)
1
2
3
4
5
6
7
8
9
10
11
def get(self, key):
    """
    :type key: int
    :rtype: int
    """
    node = self.cache.get(key)
    if not node:
        return -1

    self.move_to_head(node)
    return node.value

同时对LRUcache的基本属性为：

1
2
3
4
5
6
7
8
9
10
11
def __init__(self, capacity):
    """
    :type capacity: int
    """
    self.cache = {}
    self.size = 0
    self.capacity = capacity
    self.head = new_node()
    self.tail = new_node()
    self.head.next = self.tail
    self.tail.prev = self.head