1.leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-interview-150" rel="nofollow">题目

2.思想

3.代码

3.1 代码1

下面这是一版错误的代码。错误的原因在于逻辑不正确导致最后的代码也是不正确的。

class LRUCache:def __init__(self, capacity: int):self.time = 0 # 用于全局记录访问的时间self.num2time = {} # 数字到时间的映射self.key2val = {} # 数字到数字self.capacity = capacityself.history = [] # 用于记录操作的历史# get 也要对时间进行修改def get(self, key: int) -> int:         if self.key2val.get(key,-1) != -1:self.time += 1self.num2time[key] = self.time # 更新时间成最新的self.history.append(key)return self.key2val.get(key,-1)def put(self, key: int, value: int) -> None:self.time += 1 # 时间戳加1self.history.append(key)        # 如果目前还没有装满，那么直接放if(len(self.key2val) < self.capacity):self.key2val[key] = valueelif(self.key2val.get(key,-1)!=-1):self.key2val[key] = value # 直接更新self.num2time[key] = self.timeself.history.append(key)else: # 考虑去掉某个数            curTime = self.time# 获取左侧的时间while(self.num2time.get(self.history[0],-1)==-1):del self.history[0] # 删除 第0位 元素leftTime = self.num2time[self.history[0]]while(curTime - leftTime < self.capacity):del self.history[0] # 删除 第0位 元素while(self.num2time.get(self.history[0],-1)==-1):del self.history[0] # 删除 第0位 元素leftTime = self.num2time[self.history[0]] invalid_key = self.history[0]# print("invalid_key = ",invalid_key)# print("key2val = ",self.key2val)# print("history = ", self.history)del self.key2val[invalid_key]del self.history[0]del self.num2time[invalid_key]self.key2val[key] = valueself.num2time[key] = self.time# print("num2time = ", self.num2time)# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

错误的逻辑主要在下面这个地方：

这里的while是想用于找出该删除哪个数，但是这个逻辑并非正确
这里的curTime表示当前的时间，leftTime表示访问栈中最左侧节点的时间。二者的距离与capacity进行比较：

• 如果距离大于等于capacity，那么就表明需要把这个数删除
  这样依次判断，找出需要退出的那个数即可。