综合算法 IV | 数据结构设计

综合算法 IV | 数据结构设计

设计数据结构

面试中经常需要设计满足特定要求的数据结构。

LRU 缓存

from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = OrderedDict() def get(self, key): if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key, value): if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.capacity: self.cache.popitem(last=False)

最小栈

class MinStack: def __init__(self): self.stack = [] self.min_stack = [] def push(self, val): self.stack.append(val) if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self): val = self.stack.pop() if val == self.min_stack[-1]: self.min_stack.pop() def top(self): return self.stack[-1] def getMin(self): return self.min_stack[-1]

栈实现队列

class MyQueue: def __init__(self): self.in_stack = [] self.out_stack = [] def push(self, x): self.in_stack.append(x) def pop(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() def peek(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self): return not self.in_stack and not self.out_stack

总结

设计数据结构需要理解常见数据结构的原理，根据需求组合实现。