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
114
115
116
117
118
119
120
121
122
123
124
125

// @Title: LRU 缓存 (LRU Cache)
// @Author: 15816537946@163.com
// @Date: 2019-11-07 17:34:47
// @Runtime: 148 ms
// @Memory: 15.2 MB
/*
 * @lc app=leetcode.cn id=146 lang=golang
 *
 * [146] LRU缓存机制
 *
 * https://leetcode-cn.com/problems/lru-cache/description/
 *
 * algorithms
 * Medium (42.71%)
 * Likes:    210
 * Dislikes: 0
 * Total Accepted:    14.3K
 * Total Submissions: 33.5K
 * Testcase Example:  '["LRUCache","put","put","get","put","get","put","get","get","get"]\n[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]'
 *
 * 运用你所掌握的数据结构，设计和实现一个  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
 *
 *
 */

// 哈希表+双端链表
type Node struct {
	prev     *Node
	next     *Node
	key, val int
}

type LRUCache struct {
	Cap        int
	Head, Tail *Node
	Cache      map[int]*Node
}

func Constructor(capacity int) LRUCache {
	obj := LRUCache{
		Cap:   capacity,
		Cache: make(map[int]*Node),
	}
	obj.Head = &Node{}
	obj.Tail = &Node{}
	obj.Head.next = obj.Tail
	obj.Tail.prev = obj.Head

	return obj
}

func (this *LRUCache) addToFront(node *Node) {
	this.remove(node)
	this.add(node)
}

func (this *LRUCache) remove(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev

	node.prev = nil
	node.next = nil
}

func (this *LRUCache) add(node *Node) {
	node.prev = this.Head
	node.next = this.Head.next

	this.Head.next.prev = node
	this.Head.next = node
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.Cache[key]; ok {
		this.addToFront(node)
		return node.val
	}
	return -1
}

func (this *LRUCache) Put(key, value int) {
	if node, ok := this.Cache[key]; ok {
		node.val = value
		this.addToFront(node)
		return
	}

	node := &Node{
		key: key,
		val: value,
	}

	if this.Cap <= len(this.Cache) {
		lastNode := this.Tail.prev
		this.remove(lastNode)
		delete(this.Cache, lastNode.key)
	}

	this.add(node)
	this.Cache[key] = node
}