Skip to content

Commit 7bc6c9d

Browse files
halfrosthalfrost
committed
Add solution 146、460
1 parent 38aa0ac commit 7bc6c9d

File tree

9 files changed

+803
-0
lines changed

9 files changed

+803
-0
lines changed

‎leetcode/0146.LRU-Cache/146. LRU Cache.go

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package leetcode
2+
3+
type LRUCache struct {
4+
head, tail *Node
5+
Keys map[int]*Node
6+
Cap int
7+
}
8+
9+
type Node struct {
10+
Key, Val int
11+
Prev, Next *Node
12+
}
13+
14+
func Constructor(capacity int) LRUCache {
15+
return LRUCache{Keys: make(map[int]*Node), Cap: capacity}
16+
}
17+
18+
func (this *LRUCache) Get(key int) int {
19+
if node, ok := this.Keys[key]; ok {
20+
this.Remove(node)
21+
this.Add(node)
22+
return node.Val
23+
}
24+
return -1
25+
}
26+
27+
func (this *LRUCache) Put(key int, value int) {
28+
if node, ok := this.Keys[key]; ok {
29+
node.Val = value
30+
this.Remove(node)
31+
this.Add(node)
32+
return
33+
} else {
34+
node = &Node{Key: key, Val: value}
35+
this.Keys[key] = node
36+
this.Add(node)
37+
}
38+
if len(this.Keys) > this.Cap {
39+
delete(this.Keys, this.tail.Key)
40+
this.Remove(this.tail)
41+
}
42+
}
43+
44+
func (this *LRUCache) Add(node *Node) {
45+
node.Prev = nil
46+
node.Next = this.head
47+
if this.head != nil {
48+
this.head.Prev = node
49+
}
50+
this.head = node
51+
if this.tail == nil {
52+
this.tail = node
53+
this.tail.Next = nil
54+
}
55+
}
56+
57+
func (this *LRUCache) Remove(node *Node) {
58+
if node == this.head {
59+
this.head = node.Next
60+
node.Next = nil
61+
return
62+
}
63+
if node == this.tail {
64+
this.tail = node.Prev
65+
node.Prev.Next = nil
66+
node.Prev = nil
67+
return
68+
}
69+
node.Prev.Next = node.Next
70+
node.Next.Prev = node.Prev
71+
}

‎leetcode/0146.LRU-Cache/146. LRU Cache_test.go

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
func Test_Problem147(t *testing.T) {
9+
obj := Constructor(2)
10+
fmt.Printf("obj = %v\n", MList2Ints(&obj))
11+
obj.Put(1, 1)
12+
fmt.Printf("obj = %v\n", MList2Ints(&obj))
13+
obj.Put(2, 2)
14+
fmt.Printf("obj = %v\n", MList2Ints(&obj))
15+
param1 := obj.Get(1)
16+
fmt.Printf("param_1 = %v obj = %v\n", param1, MList2Ints(&obj))
17+
obj.Put(3, 3)
18+
fmt.Printf("obj = %v\n", MList2Ints(&obj))
19+
param1 = obj.Get(2)
20+
fmt.Printf("param_1 = %v obj = %v\n", param1, MList2Ints(&obj))
21+
obj.Put(4, 4)
22+
fmt.Printf("obj = %v\n", MList2Ints(&obj))
23+
param1 = obj.Get(1)
24+
fmt.Printf("param_1 = %v obj = %v\n", param1, MList2Ints(&obj))
25+
param1 = obj.Get(3)
26+
fmt.Printf("param_1 = %v obj = %v\n", param1, MList2Ints(&obj))
27+
param1 = obj.Get(4)
28+
fmt.Printf("param_1 = %v obj = %v\n", param1, MList2Ints(&obj))
29+
}
30+
31+
func MList2Ints(lru *LRUCache) [][]int {
32+
res := [][]int{}
33+
head := lru.head
34+
for head != nil {
35+
tmp := []int{head.Key, head.Val}
36+
res = append(res, tmp)
37+
head = head.Next
38+
}
39+
return res
40+
}

‎leetcode/0146.LRU-Cache/README.md

Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,134 @@
1+
# [146. LRU Cache](https://leetcode.com/problems/lru-cache/)
2+
3+
## 题目
4+
5+
Design a data structure that follows the constraints of a **[Least Recently Used (LRU) cache](https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU)**.
6+
7+
Implement the `LRUCache` class:
8+
9+
- `LRUCache(int capacity)` Initialize the LRU cache with **positive** size `capacity`.
10+
- `int get(int key)` Return the value of the `key` if the key exists, otherwise return `1`.
11+
- `void put(int key, int value)` Update the value of the `key` if the `key` exists. Otherwise, add the `key-value` pair to the cache. If the number of keys exceeds the `capacity` from this operation, **evict** the least recently used key.
12+
13+
**Follow up:**Could you do `get` and `put` in `O(1)` time complexity?
14+
15+
**Example 1:**
16+
17+
```
18+
Input
19+
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
20+
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
21+
Output
22+
[null, null, null, 1, null, -1, null, -1, 3, 4]
23+
24+
Explanation
25+
LRUCache lRUCache = new LRUCache(2);
26+
lRUCache.put(1, 1); // cache is {1=1}
27+
lRUCache.put(2, 2); // cache is {1=1, 2=2}
28+
lRUCache.get(1); // return 1
29+
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
30+
lRUCache.get(2); // returns -1 (not found)
31+
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
32+
lRUCache.get(1); // return -1 (not found)
33+
lRUCache.get(3); // return 3
34+
lRUCache.get(4); // return 4
35+
36+
```
37+
38+
**Constraints:**
39+
40+
- `1 <= capacity <= 3000`
41+
- `0 <= key <= 3000`
42+
- `0 <= value <= 104`
43+
- At most `3 * 104` calls will be made to `get` and `put`.
44+
45+
## 题目大意
46+
47+
运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
48+
实现 LRUCache 类：
49+
50+
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
51+
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
52+
- void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
53+
54+
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
55+
56+
## 解题思路
57+
58+
- 这一题是 LRU 经典面试题，详细解释见第三章模板。
59+
60+
## 代码
61+
62+
```go
63+
package leetcode
64+
65+
type LRUCache struct {
66+
head, tail *Node
67+
Keys map[int]*Node
68+
Cap int
69+
}
70+
71+
type Node struct {
72+
Key, Val int
73+
Prev, Next *Node
74+
}
75+
76+
func Constructor(capacity int) LRUCache {
77+
return LRUCache{Keys: make(map[int]*Node), Cap: capacity}
78+
}
79+
80+
func (this *LRUCache) Get(key int) int {
81+
if node, ok := this.Keys[key]; ok {
82+
this.Remove(node)
83+
this.Add(node)
84+
return node.Val
85+
}
86+
return -1
87+
}
88+
89+
func (this *LRUCache) Put(key int, value int) {
90+
if node, ok := this.Keys[key]; ok {
91+
node.Val = value
92+
this.Remove(node)
93+
this.Add(node)
94+
return
95+
} else {
96+
node = &Node{Key: key, Val: value}
97+
this.Keys[key] = node
98+
this.Add(node)
99+
}
100+
if len(this.Keys) > this.Cap {
101+
delete(this.Keys, this.tail.Key)
102+
this.Remove(this.tail)
103+
}
104+
}
105+
106+
func (this *LRUCache) Add(node *Node) {
107+
node.Prev = nil
108+
node.Next = this.head
109+
if this.head != nil {
110+
this.head.Prev = node
111+
}
112+
this.head = node
113+
if this.tail == nil {
114+
this.tail = node
115+
this.tail.Next = nil
116+
}
117+
}
118+
119+
func (this *LRUCache) Remove(node *Node) {
120+
if node == this.head {
121+
this.head = node.Next
122+
node.Next = nil
123+
return
124+
}
125+
if node == this.tail {
126+
this.tail = node.Prev
127+
node.Prev.Next = nil
128+
node.Prev = nil
129+
return
130+
}
131+
node.Prev.Next = node.Next
132+
node.Next.Prev = node.Prev
133+
}
134+
```

‎leetcode/0460.LFU-Cache/460. LFU Cache.go

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package leetcode
2+
3+
import "container/list"
4+
5+
type LFUCache struct {
6+
nodes map[int]*list.Element
7+
lists map[int]*list.List
8+
capacity int
9+
min int
10+
}
11+
12+
type node struct {
13+
key int
14+
value int
15+
frequency int
16+
}
17+
18+
func Constructor(capacity int) LFUCache {
19+
return LFUCache{nodes: make(map[int]*list.Element),
20+
lists: make(map[int]*list.List),
21+
capacity: capacity,
22+
min: 0,
23+
}
24+
}
25+
26+
func (this *LFUCache) Get(key int) int {
27+
value, ok := this.nodes[key]
28+
if !ok {
29+
return -1
30+
}
31+
currentNode := value.Value.(*node)
32+
this.lists[currentNode.frequency].Remove(value)
33+
currentNode.frequency++
34+
if _, ok := this.lists[currentNode.frequency]; !ok {
35+
this.lists[currentNode.frequency] = list.New()
36+
}
37+
newList := this.lists[currentNode.frequency]
38+
newNode := newList.PushBack(currentNode)
39+
this.nodes[key] = newNode
40+
if currentNode.frequency-1 == this.min && this.lists[currentNode.frequency-1].Len() == 0 {
41+
this.min++
42+
}
43+
return currentNode.value
44+
}
45+
46+
func (this *LFUCache) Put(key int, value int) {
47+
if this.capacity == 0 {
48+
return
49+
}
50+
if currentValue, ok := this.nodes[key]; ok {
51+
currentNode := currentValue.Value.(*node)
52+
currentNode.value = value
53+
this.Get(key)
54+
return
55+
}
56+
if this.capacity == len(this.nodes) {
57+
currentList := this.lists[this.min]
58+
frontNode := currentList.Front()
59+
delete(this.nodes, frontNode.Value.(*node).key)
60+
currentList.Remove(frontNode)
61+
}
62+
this.min = 1
63+
currentNode := &node{
64+
key: key,
65+
value: value,
66+
frequency: 1,
67+
}
68+
if _, ok := this.lists[1]; !ok {
69+
this.lists[1] = list.New()
70+
}
71+
newList := this.lists[1]
72+
newNode := newList.PushBack(currentNode)
73+
this.nodes[key] = newNode
74+
}

‎leetcode/0460.LFU-Cache/460. LFU Cache_test.go

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
func Test_Problem460(t *testing.T) {
9+
obj := Constructor(5)
10+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
11+
obj.Put(1, 1)
12+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
13+
obj.Put(2, 2)
14+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
15+
obj.Put(3, 3)
16+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
17+
obj.Put(4, 4)
18+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
19+
obj.Put(5, 5)
20+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
21+
22+
param1 := obj.Get(4)
23+
fmt.Printf("param_1 = %v obj.list = %v obj.map = %v obj.min = %v\n", param1, MLists2Ints(&obj), MList2Ints(&obj), obj.min)
24+
param1 = obj.Get(4)
25+
fmt.Printf("param_1 = %v obj.list = %v obj.map = %v obj.min = %v\n", param1, MLists2Ints(&obj), MList2Ints(&obj), obj.min)
26+
param1 = obj.Get(4)
27+
fmt.Printf("param_1 = %v obj.list = %v obj.map = %v obj.min = %v\n", param1, MLists2Ints(&obj), MList2Ints(&obj), obj.min)
28+
param1 = obj.Get(5)
29+
fmt.Printf("param_1 = %v obj.list = %v obj.map = %v obj.min = %v\n", param1, MLists2Ints(&obj), MList2Ints(&obj), obj.min)
30+
param1 = obj.Get(5)
31+
fmt.Printf("param_1 = %v obj.list = %v obj.map = %v obj.min = %v\n", param1, MLists2Ints(&obj), MList2Ints(&obj), obj.min)
32+
param1 = obj.Get(5)
33+
fmt.Printf("param_1 = %v obj.list = %v obj.map = %v obj.min = %v\n", param1, MLists2Ints(&obj), MList2Ints(&obj), obj.min)
34+
obj.Put(6, 6)
35+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
36+
obj.Put(7, 7)
37+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
38+
obj.Put(8, 8)
39+
fmt.Printf("obj.list = %v obj.map = %v obj.min = %v\n", MLists2Ints(&obj), MList2Ints(&obj), obj.min)
40+
}
41+
42+
func MList2Ints(lfu *LFUCache) map[int][][]int {
43+
res := map[int][][]int{}
44+
for k, v := range lfu.nodes {
45+
node := v.Value.(*node)
46+
arr := [][]int{}
47+
tmp := []int{node.key, node.value, node.frequency}
48+
arr = append(arr, tmp)
49+
res[k] = arr
50+
}
51+
return res
52+
}
53+
54+
func MLists2Ints(lfu *LFUCache) map[int][]int {
55+
res := map[int][]int{}
56+
for k, v := range lfu.lists {
57+
tmp := []int{}
58+
for head := v.Front(); head != nil; head = head.Next() {
59+
tmp = append(tmp, head.Value.(*node).value)
60+
}
61+
res[k] = tmp
62+
}
63+
return res
64+
}

0 commit comments

Comments
 (0)