本文目录
最小栈
题目描述
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) – 将元素 x 推入栈中。
- pop() – 删除栈顶的元素。
- top() – 获取栈顶元素。
- getMin() – 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
代码实现
思路：栈内的每个元素是一个元组，其中包含最小元素。
class MinStack:
def __init__(self):
self.q = []
def push(self, x):
curMin = self.getMin()
if curMin is None or x < curMin:
curMin = x
self.q.append((x, curMin))
def pop(self):
self.q.pop()
def top(self):
if len(self.q) == 0:
return None
else:
return self.q[-1][0]
def getMin(self):
if len(self.q) == 0:
return None
else:
return self.q[-1][1
LRU缓存机制
题目描述
运用你所掌握的数据结构，设计和实现一个 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
代码实现
class Node:
def __init__(self, k, v):
self.key = k
self.val = v
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {} # 缓存 key --> node
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
val = node.val
self._remove(node)
self._add(node) # 重新添加到双向链表的后端
return val
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
self._remove(node)
new_node = Node(key, value)
self._add(new_node)
if len(self.cache) > self.cap:
self._remove(self.head.next) # 移除第一个节点
def _add(self, node):
prev = self.tail.prev
prev.next = node
node.prev = prev
node.next = self.tail
self.tail.prev = node
self.cache[node.key] = node
def _remove(self, node):
prev, next_ = node.prev, node.next
prev.next = next_
next_.prev = prev
del self.cache[node.key]
实现 Trie (前缀树)
前缀树的概念：
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
题目描述
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
代码实现
class TrieNode:
def __init__(self):
self.word = False
self.children = {}
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for ch in word:
if ch in node.children:
node = node.children[ch]
else:
return False
return node.word
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for ch in prefix:
if ch in node.children:
node = node.children[ch]
else:
return False
return True
题目描述
实现一个数据结构支持以下操作：
- Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
- Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
- GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串
""。 - GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串
""。
挑战：以 O(1) 的时间复杂度实现所有操作。
代码实现
参考：Python-solution-with-detailed-comments
使用两个哈希表加一个双向链表：
from collections import defaultdict
class Node(object):
def __init__(self):
self.key_set = set()
self.prev, self.nxt = None, None
def add_key(self, key):
self.key_set.add(key)
def remove_key(self, key):
self.key_set.remove(key)
def get_any_key(self):
if self.key_set:
result = self.key_set.pop()
self.add_key(result)
return result
else:
return None
def count(self):
return len(self.key_set)
def is_empty(self):
return len(self.key_set) == 0
class DoubleLinkedList(object):
def __init__(self):
self.head_node, self.tail_node = Node(), Node()
self.head_node.nxt, self.tail_node.prev = self.tail_node, self.head_node
def insert_after(self, x):
node, temp = Node(), x.nxt
x.nxt, node.prev = node, x
node.nxt, temp.prev = temp, node
return node
def insert_before(self, x):
return self.insert_after(x.prev)
def remove(self, x):
prev_node = x.prev
prev_node.nxt, x.nxt.prev = x.nxt, prev_node
return
def get_head(self):
return self.head_node.nxt
def get_tail(self):
return self.tail_node.prev
def get_sentinel_head(self):
return self.head_node
def get_sentinel_tail(self):
return self.tail_node
class AllOne(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.dll, self.key_counter = DoubleLinkedList(), defaultdict(int)
self.node_freq = {0: self.dll.get_sentinel_head()}
def _rmv_key_pf_node(self, pf, key):
node = self.node_freq[pf]
node.remove_key(key)
if node.is_empty():
self.dll.remove(node)
self.node_freq.pop(pf)
return
def inc(self, key):
self.key_counter[key] += 1
cf, pf = self.key_counter[key], self.key_counter[key]-1
if cf not in self.node_freq:
# No need to test if pf = 0 since
# frequency zero points to sentinel node
self.node_freq[cf] = self.dll.insert_after(self.node_freq[pf])
self.node_freq[cf].add_key(key)
if pf > 0:
self._rmv_key_pf_node(pf, key)
def dec(self, key):
if key in self.key_counter:
self.key_counter[key] -= 1
cf, pf = self.key_counter[key], self.key_counter[key]+1
if self.key_counter[key] == 0:
self.key_counter.pop(key)
if cf != 0:
if cf not in self.node_freq:
self.node_freq[cf] = self.dll.insert_before(
self.node_freq[pf])
self.node_freq[cf].add_key(key)
self._rmv_key_pf_node(pf, key)
def getMaxKey(self):
"""
Returns one of the keys with maximal value.
:rtype: str
"""
return self.dll.get_tail().get_any_key() if self.dll.get_tail().count() > 0 else ""
def getMinKey(self):
"""
Returns one of the keys with Minimal value.
:rtype: str
"""
return self.dll.get_head().get_any_key() if self.dll.get_tail().count() > 0 else ""