146. LRU Cache
Tags:
Medium
Skills:
Linked List
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bạn cần thiết kế một cấu trúc dữ liệu hỗ trợ hai thao tác sau với TC: O(1)
Approach
map đẻ lưu key và valueget(value) hoặc put(key,value) Cách này tận dụng đặc điểm của Map trong JavaScript/TypeScript, không phải HashMap thông thường như trong Java.
Solution
1class LRUCache {
2 capacity: number;
3 map: Map<number, number>;
4 constructor(capacity: number) {
5 this.capacity = capacity;
6 this.map = new Map();
7 }
8
9 get(key: number): number {
10 if (!this.map.has(key)) return -1;
11 const value = this.map.get(key);
12 this.map.delete(key);
13 this.map.set(key, value)
14 return value;
15 }
16
17 put(key: number, value: number): void {
18 if (this.map.has(key)) {
19 this.map.delete(key)
20 }
21
22 this.map.set(key, value);
23 if (this.map.size > this.capacity) {
24 const lru_key = this.map.keys().next().value;
25 this.map.delete(lru_key)
26 }
27 }
28}
29
30/**
31 * Your LRUCache object will be instantiated and called as such:
32 * var obj = new LRUCache(capacity)
33 * var param_1 = obj.get(key)
34 * obj.put(key,value)
35 */Map để giải quyết bài toánthis.map.set(key, value) trong hàm put có hai mục đích quan trọng khi chỉ sử dụng Map để cài đặt LRU Cache:this.map.set(key, value) sẽ cập nhật giá trị, đồng thời đẩy key này về cuối Map (thể hiện là "mới sử dụng gần nhất").Time and space complexity
Time complexity
Space Complexity
Solution
1class Node {
2 key: number;
3 value: number;
4 prev: Node | null = null;
5 next: Node | null = null;
6 constructor(key: number, value: number) {
7 this.key = key;
8 this.value value;
9 }
10}
11
12class LRUCache {
13 capacity: number;
14 cache: Map<number, Node>;
15 head: Node;
16 tail: Node;
17
18 constructor(capacity: number) {
19 this.capacity = capacity;
20 this.cache = new Map();
21
22 this.head = new Node(0, 0)
23 this.tail = new Node(0, 0);
24 this.head.next = this.tail;
25 this.tail.prev = this.head;
26 }
27
28 get(key: number): number {
29 const node = this.cache.get(key);
30 if(!node) return -1;
31 this.moveToHead(node);
32 return node.value;
33 }
34
35 put(key: number, value: number): void {
36 let node = this.cache.get(key);
37 if(node) {
38 node.value = value;
39 this.moveToHead(node);
40 } else {
41 node = new Node(key, value)
42 this.cache.set(key, node)
43 this.addToHead(node)
44 if(this.cache.size > this.capacity) {
45 const tail = this.removeTail();
46 if(tail) this.cache.delete(tail.key);
47 }
48 }
49 }
50
51 addToHead(node: Node): void {
52 node.prev = this.head;
53 node.next = this.head.next;
54 if(this.head.next) this.head.next.prev = node;
55 this.head.next = node;
56 }
57
58 removeNode(node: Node): void {
59 if(node.prev) node.prev.next = node.next;
60 if(node.next) node.next.prev = node.prev;
61 }
62
63 moveToHead(node: Node): void {
64 this.removeNode(node);
65 this.addToHead(node);
66 }
67
68 removeTail(): Node | null {
69 if(!this.tail.prev || this.tail.preve === this.head) return null;
70 const node = this.tail.prev;
71 this.removeNode(node);
72 return node;
73 }
74}
75
76/**
77 * Your LRUCache object will be instantiated and called as such:
78 * var obj = new LRUCache(capacity)
79 * var param_1 = obj.get(key)
80 * obj.put(key,value)
81 */1if(this.head.next) this.head.next.prev = node;có ý nghĩa như sau: