题解 | #牛牛的门票缓存系统#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param operations string字符串一维数组 
# @param data int整型二维数组 
# @param capacity int整型 
# @return int整型一维数组
#
class Solution:
    def performOperation(self , operations: List[str], data: List[List[int]], capacity: int) -> List[int]:
        # write code here
        # 函数 getTicket 和 putTicket 必须以平均时间复杂度 O(1) 运行。
        # 也就是不能搜索，获取和修改只能哈希
        # 如果插入操作导致缓存中门票数量超过容量 capacity，则应该逐出最不经常使用的门票。
        # 这里理解最不经常使用就是使用次数最少的
        class TicketCache:
            def __init__(self, capacity):
                self.capacity = capacity
                # 用字典来记录tickid，以及操作序号，便于查询
                self.d = dict()
                self.dcnt = dict() # 记录使用次数
                self.size = 0
            
            def getTicket(self, ticketId):
                if ticketId in self.d:
                    self.dcnt[ticketId] += 1 # 更新一次 
                    return self.d[ticketId]
                else:
                    return -1
            
            def putTicket(self, ticketId, ticketInfo):
                if self.capacity == 0:
                        return # 直接结束
                        
                if ticketId in self.d: # update
                    self.d[ticketId] = ticketInfo
                    self.dcnt[ticketId] += 1 # 更新一次 

                else: # 需要添加，首先检查capacity
                    if self.size == self.capacity: # 已经很满了，先删除
                        # 找到cnt最小的对
                        tempd = sorted(self.dcnt.items(), key = lambda x: x[1])
                        to_remove_id, _ = tempd[0] # (id, cnt) # 最先被操作的
                        del self.dcnt[to_remove_id]
                        del self.d[to_remove_id]
                        self.size -= 1
                    self.size += 1 
                    self.d[ticketId] = ticketInfo
                    self.dcnt[ticketId] = 0 # 初始化
        
        ticket = TicketCache(capacity)
        ans = []
        for i in range(len(operations)):
            tdata = data[i]
            if operations[i] == "putTicket":
                ticket.putTicket(tdata[0], tdata[1])
            else: # getTicket
                ret = ticket.getTicket(tdata[0])
                ans.append(ret)
            print(ticket.d)
        return ans

这题题目不难，但是容易有歧义，题目说移除最不常使用的，我开始以为是距离现在最远的上次操作的ticket，其实只是移除操作次数最少的ticket。注意这点。要实现O（1）put和get，考虑使用dict。一个dict来记录数据，另一个来记录操作次数。