分析需求

Get

  1. 如果节点存在：
  • 将节点从当前位置删除
  • 将节点移动到第一个位置
  1. 如果节点不存在: 直接返回-1

Put

  1. 如果节点存在：
  • 更新value
  • 将节点从当前位置删除
  • 将节点移动到第一个位置
  1. 如果节点不存在：size < cap
  • 将节点直接移动到第一个位置
  • 节点放入map
  • size+1
  1. 如果节点不存在：size >= cap (其实不存在>情况，这里方便理解)
  • 将节点直接移动到第一个位置
  • 将末尾节点删除
  • 将末尾节点从map删除

总结

归纳下来主要有俩个操作：

  • 将节点直接移动到第一个位置
  • 将节点从当前位置删除
  • 备注：为了便于操作， 我们将tail和head设置为虚拟节点，这样就不需要考虑边界情况，操作起来非常nice

实现

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// 节点
type Node struct {
    Key int
    Value int
    Next *Node
    Pre *Node
}

type LRUCache struct {
    Cap int
    Size int
    NodeMap map[int]*Node
    // 头部指针
    Head *Node
    // 末尾指针
    Tail *Node
}

func Constructor(capacity int) LRUCache {
    lru := LRUCache{
        Cap: capacity,
        Size: 0,
    }
    lru.NodeMap = make(map[int]*Node, 0)
    lru.Tail = &Node{}
    lru.Head = &Node{}

    return lru
}

// 将节点移动放置到头部节点
func (this *LRUCache) moveToHead(node *Node) {
    if this.Size == 0 {
        this.Head.Next = node
        node.Pre = this.Head
        this.Tail.Pre = node
        node.Next = this.Tail
        return
    }

    // 节点的Next是之前头部节点的next
    node.Next = this.Head.Next
    // 之前的第一个节点的pre节点是当前节点
    this.Head.Next.Pre = node
    // 节点的pre节点是头部指针
    node.Pre = this.Head
    // 头部指针next指向node
    this.Head.Next = node
}

// 删除节点
func (this *LRUCache) delNode(node *Node) {
    node.Pre.Next = node.Next
    node.Next.Pre = node.Pre
}


func (this *LRUCache) Get(key int) int {
    node, ok := this.NodeMap[key]
    if !ok {
        return -1
    }

    // 1. 将节点从当前位置删除
    this.delNode(node)

    // 2. 将该节点移动到头部位置
    this.moveToHead(node)

    return node.Value
}


func (this *LRUCache) Put(key int, value int)  {
    existNode, ok := this.NodeMap[key]
    if ok {
        // 如果已经存在
        existNode.Value = value

        // 从当前位置删除
        this.delNode(existNode)
        // 移动到头部位置
        this.moveToHead(existNode)

        return
    }


    node := &Node{
        Key: key,
        Value: value,
    }
    // 首先加载到map中
    this.NodeMap[key] = node

    // 1. 如果size < cap
    if this.Size < this.Cap {
        // 1.1 将节点放到头部位置
        this.moveToHead(node)
        // 1.2 size+1
        this.Size++
    } else {
        // 2. 如果size = cap
        // 2.1 讲节点放到头部位置
        this.moveToHead(node)

        // 2.2 删除末尾节点
        nowTailPre := this.Tail.Pre
        this.delNode(nowTailPre)
        // 从map里面删除
        delete(this.NodeMap, nowTailPre.Key)
    }
}

飞向：leetcode-lru