综合算法 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(lastFalse)最小栈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总结设计数据结构需要理解常见数据结构的原理根据需求组合实现。