数据结构设计
146. LRU 缓存机制
LRU包含一个双向链表和一个哈希表，双向链表用于保存节点的顺序，哈希表使得查找效率在常数级时间复杂度。
- 插入元素：首先检查LRU是否到达存储上限，若是则需要删除最久未使用的元素，将其从双向链表和哈希表中删除，再在双向链表头部添加新的元素；如果要插入的
key已经存在，则更新其值并在双向链表中将其节点提前。
- 查找元素：如果元素存在，则需要在双向链表中将该元素的节点提前。
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
| class LRUCache {
class Node {
public int key;
public int val;
public Node prev;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
class DoubleList {
public Node head;
public Node tail;
public int size;
public DoubleList() {
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
this.size = 0;
}
public void add(Node x) {
x.next = head.next;
head.next.prev = x;
x.prev = head;
head.next = x;
this.size++;
}
public void del(Node x) {
x.next.prev = x.prev;
x.prev.next = x.next;
this.size--;
}
public Node pop() {
Node x = tail.prev;
del(x);
return x;
}
}
public HashMap<Integer, Node> map;
public DoubleList list;
public int capacity;
public LRUCache(int capacity) {
this.map = new HashMap<>();
this.list = new DoubleList();
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node x = map.get(key);
list.del(x);
list.add(x);
return x.val;
}
public void put(int key, int value) {
Node x = new Node(key, value);
if (map.containsKey(key)) {
Node d = map.get(key);
list.del(d);
} else if (list.size==capacity) {
Node d = list.pop();
map.remove(d.key);
}
map.put(key, x);
list.add(x);
}
}
|
208. 实现 Trie (前缀树)
Trie树节点包括一个布尔类型的值，用来标记这个节点是否代表一个词的末尾，以及一个长度为N的数组表示所有可能出现的字符，例如这里需要26个元素代表26个小写字母。
- 插入单词：把单词拆分成一个一个字符，首字母建立Trie根节点，依次遍历，如果字符的节点已经存在，什么都不做继续遍历，如果字符节点不存在，在当前树的对应节点中新建节点。到最后，标记为单词的末尾。
- 查询是否是单词：把单词拆分成一个一个字符，从头查询字符在树中对应子节点是否存在。如果不存在，返回
false。最后要检查其末尾标记是否为真。
- 查询是否是前缀：与查询是否是单词类似，区别是无需判断是否有末尾的标记。
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
| class Trie {
class Node {
public Node[] ch;
public boolean isEnd;
public Node() {
this.ch = new Node[26];
}
}
public Node root;
public Trie() {
root = new Node();
}
public void insert(String word) {
Node trie = root;
for (int i=0; i<word.length(); i++) {
char c = word.charAt(i);
if (trie.ch[c-'a']==null) trie.ch[c-'a'] = new Node();
trie = trie.ch[c-'a'];
}
trie.isEnd = true;
}
public boolean search(String word) {
Node trie = root;
for (int i=0; i<word.length(); i++) {
char c = word.charAt(i);
if (trie.ch[c-'a']==null) return false;
trie = trie.ch[c-'a'];
}
return trie.isEnd;
}
public boolean startsWith(String prefix) {
Node trie = root;
for (int i=0; i<prefix.length(); i++) {
char c = prefix.charAt(i);
if (trie.ch[c-'a']==null) return false;
trie = trie.ch[c-'a'];
}
return true;
}
}
|