true
刷刷算法
true
https://kaviilee.github.io/blog/2021/03/30/%E5%88%B7%E5%88%B7%E7%AE%97%E6%B3%95/
none
none
是算法耶！
- 实现 Trie （前缀树）
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
- Trie() 初始化前缀树对象。
- void insert(String word) 向前缀树中插入字符串 word 。
- boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
- boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
class Trie {
root: { [key: string]: any }
constructor() {
this.root = Object.create(null)
}
insert(word: string): void {
let node = this.root;
for (const w of word) {
if (!node[w]) {
node[w] = Object.create(null);
}
node = node[w]
}
node.isEnd = true
}
searchPrefix(word: string) {
let node = this.root;
for (const w of word) {
node = node[w];
if (!node) return null
}
return node
}
search(word: string): boolean {
let node = this.searchPrefix(word)
return !!node && !!node.isEnd;
}
startWith(prefix: string): boolean {
return !!this.searchPrefix(prefix)
}
}
|
- 实现 LRU 算法
class LRUCache {
cache: Map<number, number>;
capacity: number;
constructor(capacity: number) {
this.cache = new Map<number, number>()
this.capacity = capcity;
}
put(key: number, value: number): void {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
this.cache.delete(this.cache.keys().next().value)
}
this.cache.set(key, value)
}
get(key: number): number {
if (this.cache.has(key)) {
const val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val);
return val
}
return -1
}
}
|
