leetcode中的一道题目:
设计和实现一个 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); // 返回 1cache.put(3, 3); // 该操作会使得密钥 2 作废cache.get(2); // 返回 -1 (未找到)cache.put(4, 4); // 该操作会使得密钥 1 作废cache.get(1); // 返回 -1 (未找到)cache.get(3); // 返回 3cache.get(4); // 返回 4
实现一
解题思路不多说了,主要是hash加双向链表,具体详见如下代码:
type node struct { key int value uint pre *node next *node}type LRUcache struct { cap int m map[int]*node header *node rear *node}func NewLRUcache(len int) *LRUcache { if len <= 0 { return nil } m := make(map[int]*node, len) return &LRUcache{cap: len, m: m}}func (c *LRUcache) Get(key int) int { if v, ok := c.m[key]; ok { //delete this node if v.pre != nil { v.pre.next = v.next if v.next != nil { v.next.pre = v.pre } else { // set new rear c.rear = v.pre } //move to head v.next = c.header v.pre = nil c.header.pre = v c.header = v } //else do nothing return int(v.value) } return -1}func (c *LRUcache) Put(key int, value uint) { // modify if v, ok := c.m[key]; ok { //delete this node if v.pre != nil { v.pre.next = v.next if v.next != nil { v.next.pre = v.pre } else { // set new rear c.rear = v.pre } //move to head v.next = c.header v.pre = nil c.header.pre = v c.header = v } //else do nothing v.value = value } // check capacity before adding if len(c.m) >= c.cap { // remove the last if c.rear != nil { // header == rear while c.rear.pre == nil if c.rear.pre != nil { c.rear.pre.next = nil delete(c.m, c.rear.key) c.rear = c.rear.pre } else { c.rear = nil c.header = nil } } } // add if c.header == nil { c.header = &node{key: key, value: value} c.rear = c.header c.m[key] = c.header } else { newnode := &node{key: key, value: value} newnode.next = c.header c.header.pre = newnode c.header = newnode c.m[key] = newnode } return}
调试代码:
func main() { obj := NewLRUcache(2) if obj == nil { return } fmt.Println("Set 1") obj.Put(1, 1) fmt.Println("Set 2") obj.Put(2, 2) fmt.Println("Get 1 return", obj.Get(1)) fmt.Println("Set 3") obj.Put(3, 3) fmt.Println("Get 2 return", obj.Get(2)) fmt.Println("Set 4") obj.Put(4, 4) fmt.Println("Get 1 return", obj.Get(1)) fmt.Println("Get 3 return", obj.Get(3)) fmt.Println("Get 4 return", obj.Get(4))}
输出:
Set 1Set 2Get 1 return 1Set 3Get 2 return -1Set 4Get 1 return -1Get 3 return 3Get 4 return 4
编码很容易,调试的时候倒是遇到了几个小问题,各种指针指来指去,很容易出错,还到处判断头指针是否是空,尾指针是否为空等等。。。
想起之前看过Linux大神Linus Torvalds的代码的品味问题,提到如何优雅的写链表,故重新优化如下:
实现二
直接上代码:
type node struct { key int value uint pre *node next *node}type LRUcache struct { cap int m map[int]*node header *node rear *node}func NewLRUcache(len int) *LRUcache { if len <= 0 { return nil } m := make(map[int]*node, len) head := &node{} tail := &node{} head.next = tail tail.pre = head return &LRUcache{cap: len, m: m, header:head, rear:tail}}func (c *LRUcache) Get(key int) int { if v, ok := c.m[key]; ok { //remove v.pre.next = v.next v.next.pre = v.pre //add to head v.pre = c.header v.next = c.header.next c.header.next.pre = v c.header.next = v return int(v.value) } return -1}func (c *LRUcache) Put(key int, value uint) { // modify if v, ok := c.m[key]; ok { //remove v.pre.next = v.next v.next.pre = v.pre //add to head v.pre = c.header v.next = c.header.next c.header.next.pre = v c.header.next = v v.value = value } // check capacity before adding if len(c.m) >= c.cap { // remove the last remove := c.rear.pre remove.pre.next = remove.next remove.next.pre = remove.pre //delete from hash delete(c.m, remove.key) } // add newnode := &node{key: key, value: value} c.header.next.pre = newnode newnode.next = c.header.next c.header.next = newnode newnode.pre = c.header c.m[key] = newnode return}
再重新提取公共函数,进一步去优化:
type node struct { key int value uint pre *node next *node}type LRUcache struct { cap int m map[int]*node header *node rear *node}func NewLRUcache(len int) *LRUcache { if len <= 0 { return nil } m := make(map[int]*node, len) head := &node{} tail := &node{} head.next = tail tail.pre = head return &LRUcache{cap: len, m: m, header:head, rear:tail}}func (c *LRUcache) moveToHeader(v *node) { //remove v.pre.next = v.next v.next.pre = v.pre //add to head v.pre = c.header v.next = c.header.next c.header.next.pre = v c.header.next = v}func (c *LRUcache) Get(key int) int { if v, ok := c.m[key]; ok { c.moveToHeader(v) return int(v.value) } return -1}func (c *LRUcache) Put(key int, value uint) { // modify if v, ok := c.m[key]; ok { c.moveToHeader(v) v.value = value } // check capacity before adding if len(c.m) >= c.cap { // remove the last remove := c.rear.pre remove.pre.next = remove.next remove.next.pre = remove.pre //delete from hash delete(c.m, remove.key) } // add newnode := &node{key: key, value: value} c.header.next.pre = newnode newnode.next = c.header.next c.header.next = newnode newnode.pre = c.header c.m[key] = newnode return}
大功告成!!
从代码可以看到,在操作链表的时候已经不需要判断指针是否为空了,因为利用两个空节点来存储头和尾。
即链表变化为:
to
文章来源:智云一二三科技
文章标题:如何优雅的操作链表
文章地址:https://www.zhihuclub.com/7216.shtml