golang刷leetcode 经典（1） LRU缓存机制

golangLeetcode

发布于 2022-08-02 17:16:47

3840

发布于 2022-08-02 17:16:47

文章被收录于专栏：golang算法架构leetcode技术php

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

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

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

示例:

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

解题思路：

1，存储和查找

看到题目要我们实现一个可以存储 key-value 形式数据的数据结构，并且可以记录最近访问的 key 值。首先想到的就是用字典来存储 key-value 结构，这样对于查找操作时间复杂度就是 O(1)O(1)。

但是因为字典本身是无序的，所以我们还需要一个类似于队列的结构来记录访问的先后顺序，这个队列需要支持如下几种操作：

在末尾加入一项

去除最前端一项

将队列中某一项移到末尾

首先考虑列表结构。

2，LRU的实现

利用双向链表实现

双向链表有一个特点就是它的链表是双路的，我们定义好头节点和尾节点，然后利用先进先出（FIFO），最近被放入的数据会最早被获取。其中主要涉及到添加、访问、修改、删除操作。首先是添加，如果是新元素，直接放在链表头上面，其他的元素顺序往下移动；访问的话，在头节点的可以不用管，如果是在中间位置或者尾巴，就要将数据移动到头节点；修改操作也一样，修改原值之后，再将数据移动到头部；删除的话，直接删除，其他元素顺序移动；

type LRUCache struct {
    capacity int
    len int
    hashMap map[int]*Node
    head  *Node
    tail  *Node
}

type Node struct{
    Prev *Node
    Next *Node
    Val int
    Key int
}


func Constructor(capacity int) LRUCache {
    m:=make(map[int]*Node)
    lru:= LRUCache{capacity:capacity,hashMap:m,head:&Node{},tail:&Node{}}
    lru.head.Next=lru.tail
    lru.tail.Prev=lru.head
    return lru
}


func (this *LRUCache) Get(key int) int {
    if v,ok:=this.hashMap[key];ok{
       v.Prev.Next=v.Next
       v.Next.Prev=v.Prev
       n:=this.head.Next
       this.head.Next=v
       v.Prev=this.head
       n.Prev=v
       v.Next=n
       return v.Val
    }
    return -1
}


func (this *LRUCache) Put(key int, value int)  {
    if v,ok:=this.hashMap[key];ok{
       v.Prev.Next=v.Next
       v.Next.Prev=v.Prev
       n:=this.head.Next
       this.head.Next=v
       v.Prev=this.head
       n.Prev=v
       v.Next=n 
       v.Val=value
       return  
    }
    if this.len<this.capacity{
       this.len++
       node:=&Node{
           Val:value,
           Key:key,
       }
       this.hashMap[key]=node
       n:=this.head.Next
       this.head.Next=node
       node.Prev=this.head
       node.Next=n
       n.Prev=node
    }else{
        t:=this.tail.Prev
        this.tail.Prev.Prev.Next=this.tail
        this.tail.Prev= this.tail.Prev.Prev
        t.Val=value
        delete(this.hashMap,t.Key)
        t.Key=key
        this.hashMap[key]=t
        hn:=this.head.Next
        this.head.Next=t
        t.Prev=this.head
        t.Next=hn
        hn.Prev=t
    }
    return
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-12-15，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法