专栏首页福大大架构师每日一题2020-09-18:LRU手撸,说下时间复杂度和空间复杂度。
原创

2020-09-18:LRU手撸,说下时间复杂度和空间复杂度。

福哥答案2020-09-18:

方法:哈希表 + 双向链表。

时间复杂度:对于 put 和 get 都是 O(1)。

空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity+1 个元素。

代码用go语言编写,代码如下:

package test40_lru

import (
    "fmt"
    "testing"
)

/*
哈希表 + 双向链表
时间复杂度:对于 put 和 get 都是 O(1)O(1)。
空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity+1 个元素。
*/
//https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
//go test -v -test.run TestLru
func TestLru(t *testing.T) {
    cache := NewLRUCache(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

}

type LRUCache struct {
    size       int
    capacity   int
    cache      map[int]*DLinkedNode
    head, tail *DLinkedNode
}

type DLinkedNode struct {
    key, value int
    prev, next *DLinkedNode
}

func NewDLinkedNode(key, value int) *DLinkedNode {
    return &DLinkedNode{
        key:   key,
        value: value,
    }
}

func NewLRUCache(capacity int) LRUCache {
    l := LRUCache{
        cache:    map[int]*DLinkedNode{},
        head:     NewDLinkedNode(0, 0),
        tail:     NewDLinkedNode(0, 0),
        capacity: capacity,
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

//获取元素
func (f *LRUCache) Get(key int) int {
    //如果缓存里未找到元素
    if _, ok := f.cache[key]; !ok {
        fmt.Println(-1)
        return -1
    }

    //缓存里有元素
    node := f.cache[key]

    //如果 key 存在,先通过哈希表定位,再移到头部
    f.moveToHead(node)
    fmt.Println(node.value)
    return node.value
}

//放入元素
func (f *LRUCache) Put(key int, value int) {
    //如果缓存里没有元素
    if _, ok := f.cache[key]; !ok {
        node := NewDLinkedNode(key, value)
        f.cache[key] = node
        //放在头部
        f.addToHead(node)
        f.size++
        //如果元素个数大于容量,需要删除元素
        if f.size > f.capacity {
            //删除链表尾部
            removed := f.removeTail()
            //删除map中的key
            delete(f.cache, removed.key)
            f.size--
        }
    } else { //缓存里有元素
        //获取元素
        node := f.cache[key]
        //修改值
        node.value = value
        //移动到链表头
        f.moveToHead(node)
    }
}

//添加到头节点
func (f *LRUCache) addToHead(node *DLinkedNode) {
    node.prev = f.head
    node.next = f.head.next
    f.head.next.prev = node
    f.head.next = node
}

//删除节点
func (f *LRUCache) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

//移动到头节点
func (f *LRUCache) moveToHead(node *DLinkedNode) {
    f.removeNode(node)
    f.addToHead(node)
}

//删除尾部
func (f *LRUCache) removeTail() *DLinkedNode {
    node := f.tail.prev
    f.removeNode(node)
    return node
}

执行结果如下:

***

[评论](https://user.qzone.qq.com/3182319461/blog/1600382890)

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2020-10-12:在做分布式集群时候一般会产生什么问题?

    福大大架构师每日一题
  • 2020-09-05:虚拟内存知道么?什么时候使用虚拟内存?

    2020-09-05:虚拟内存知道么?什么时候使用虚拟内存?虚拟内存除了扩大内存还有什么用?

    福大大架构师每日一题
  • 2020-08-19:TCP是通过什么机制保障可靠性的?

    福哥口诀法:校(jiao)序确重拥流连(tcp可靠性保障机制:校验、序号、确认、重传、拥塞、流量、连接)

    福大大架构师每日一题
  • 力扣739——每日温度

    根据每日气温列表,请重新生成一个列表,对应位置的输入是你需要再等待多久,温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

    健程之道
  • WeTest功能优化第3期:业内首创,有声音的云真机

    原文链接:https://wetest.qq.com/lab/view/419.html

    WeTest质量开放平台团队
  • WeTest功能优化第3期:业内首创,有声音的云真机

    ? 第3期功能优化目录 【云真机远程调试】音频同步传输实现测试有声 【兼容性测试报告】新增视频助力动态定位问题 【云真机远程调试】菜单栏优化助力机型选择 本期...

    WeTest质量开放平台团队
  • SAP CRM数据库表COMM_PR_FRG_ROD的存储逻辑

    For FRAGMENT_TYPE, you can get its settype id by guid from table below:

    Jerry Wang
  • npm 创建 node.js 项目

    故,使用npm 可以对象项目的操作 在package.json中,script键可以直接项目进行操作

    一个会写诗的程序员
  • 关于如何自定义 Aspcms 的日期显示的样式

    搜索:Function formatDate(Byval t,Byval ftype) 找到

    Savalone

扫码关注云+社区

领取腾讯云代金券