设计题专题

706. 设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。 get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。 remove(key)：如果映射中存在这个键，删除这个数值对

1.关键是以下2点

1.hash方法设置，简单的话就是对素数取模

2.碰撞解决，有点拉链法的感觉

class Bucket: def __init__(self): self.data=[] def get(self,key): for (k,v) in self.data: if k==key: return v return -1 def update(self,key,value): flag=False for i,kv in enumerate(self.data): if kv[0]==key: self.data[i]=(key,value) flag=True if not flag:self.data.append((key,value)) def remove(self,key): for i,kv in enumerate(self.data): if kv[0]==key: del self.data[i] class MyHashMap: def __init__(self): self.hash_space=2069 self.hash_table=[Bucket() for _ in range(self.hash_space)] def put(self, key: int, value: int) -> None: self.hash_table[key%self.hash_space].update(key,value) def get(self, key: int) -> int: return self.hash_table[key%self.hash_space].get(key) def remove(self, key: int) -> None: self.hash_table[key%self.hash_space].remove(key)

641. 设计循环双端队列

设计实现双端队列。 你的实现需要支持以下操作：

MyCircularDeque(k)：构造函数,双端队列的大小为k。 insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。 insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。 deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。 deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。 getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。 getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。 isEmpty()：检查双端队列是否为空。 isFull()：检查双端队列是否满了。

1.每个操作都是o(1)时间

队列判空：front==last

队列判满：(last+1)%len==front

class MyCircularDeque: def __init__(self, k: int): self.front=0 self.last=0 self.length=k+1 self.arr=[0 for _ in range(self.length)] def insertFront(self, value: int) -> bool: if self.isFull():return False self.front=(self.front-1+self.length)%self.length self.arr[self.front]=value return True def insertLast(self, value: int) -> bool: if self.isFull():return False self.arr[self.last]=value self.last=(self.last+1)%self.length return True def deleteFront(self) -> bool: if self.isEmpty():return False self.front=(self.front+1)%self.length return True def deleteLast(self) -> bool: if self.isEmpty():return False self.last=(self.last-1+self.length)%self.length return True def getFront(self) -> int: if self.isEmpty():return -1 return self.arr[self.front] def getRear(self) -> int: if self.isEmpty():return -1 return self.arr[(self.last-1+self.length)%self.length] def isEmpty(self) -> bool: return self.front==self.last def isFull(self) -> bool: return (self.last+1)%self.length==self.front

622. 设计循环队列

 待做：lru lfu（抖音面试题）lc381

class MyCircularQueue: def __init__(self, k: int): self.front=0 self.last=0 self.length=k+1 self.arr=[0 for _ in range(self.length)] def enQueue(self, value: int) -> bool: if self.isFull():return False self.arr[self.last]=value self.last=(self.last+1)%self.length return True def deQueue(self) -> bool: if self.isEmpty():return False self.front=(self.front+1+self.length)%self.length return True def Front(self) -> int: if self.isEmpty():return -1 return self.arr[self.front] def Rear(self) -> int: if self.isEmpty():return -1 return self.arr[(self.last-1+self.length)%self.length] def isEmpty(self) -> bool: return self.last==self.front def isFull(self) -> bool: return (self.last+1)%self.length==self.front

面试题 16.25. LRU缓存

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

1.OrderedDict,有序字典

2.完全自己实现

hash+双向链表

3.dict+list实现，面试写这种

class LRUCache: def __init__(self, capacity: int): self.d=collections.OrderedDict() self.size=capacity def get(self, key: int) -> int: if key in self.d:self.d.move_to_end(key) return self.d.get(key,-1) def put(self, key: int, value: int) -> None: self.d[key]=value self.d.move_to_end(key) if len(self.d)>self.size: self.d.popitem(last=False ) class Listnode: def __init__(self,key=None,value=None): self.key=key self.value=value self.pre=None self.next=None class LRUCache: def __init__(self, capacity: int): self.capacity=capacity self.d={} self.head=Listnode() self.tail=Listnode() self.head.next=self.tail self.tail.pre=self.head def move_node_to_tail(self, key): node=self.d[key] node.pre.next=node.next node.next.pre=node.pre node.pre=self.tail.pre node.next=self.tail self.tail.pre.next=node self.tail.pre=node def get(self, key: int) -> int: if key in self.d:self.move_node_to_tail(key) res=self.d.get(key,-1) return res.value if res!=-1 else res def put(self, key: int, value: int) -> None: if key in self.d: self.d[key].value=value self.move_node_to_tail(key) else: if len(self.d)==self.capacity: self.d.pop(self.head.next.key) self.head.next=self.head.next.next self.head.next.pre=self.head new=Listnode(key,value) self.d[key]=new new.pre=self.tail.pre new.next=self.tail self.tail.pre.next=new self.tail.pre=new class LRUCache: def __init__(self, capacity: int): self.cache = {} self.List = [] self.capacity = capacity def get(self, key: int) -> int: if key in self.cache: self.List.remove(key) self.List.append(key) return self.cache[key] else : return -1 def put(self, key: int, value: int) -> None: if len(self.cache) < self.capacity: if key in self.cache: self.cache[key] = value self.List.remove(key) self.List.append(key) else: self.cache[key] = value self.List.append(key) else: if key in self.cache: self.cache[key] = value self.List.remove(key) self.List.append(key) else: self.cache.pop(self.List[0]) self.List.remove(self.List[0]) self.cache[key] = value self.List.append(key)