【LeetCode】146. LRU缓存

1.题目

2.思想

3.代码

3.1 代码1

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

class LRUCache:
    def __init__(self, capacity: int):
        self.time = 0 # 用于全局记录访问的时间
        self.num2time = {} # 数字到时间的映射
        self.key2val = {} # 数字到数字
        self.capacity = capacity
        self.history = [] # 用于记录操作的历史

    # get 也要对时间进行修改
    def get(self, key: int) -> int:         
        if self.key2val.get(key,-1) != -1:
            self.time += 1
            self.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 # 时间戳加1
        self.history.append(key)        
        # 如果目前还没有装满，那么直接放
        if(len(self.key2val) < self.capacity):
            self.key2val[key] = value
        elif(self.key2val.get(key,-1)!=-1):
            self.key2val[key] = value # 直接更新
            self.num2time[key] = self.time
            self.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] = value
        self.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，那么就表明需要把这个数删除
  这样依次判断，找出需要退出的那个数即可。