• 注册
    • 查看作者
    • 134. LRU Cache

      领扣:134. LRU Cache

      Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

      • get(key) Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

      • set(key, value) Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

      Finally, you need to return the data from each get.

      Example

      Example1

      Input:
      LRUCache(2)
      set(2, 1)
      set(1, 1)
      get(2)
      set(4, 1)
      get(1)
      get(2)
      Output: [1,-1,1]
      Explanation:
      cache cap is 2,set(2,1),set(1, 1),get(2) and return 1,set(4,1) and delete (1,1),because (1,1)is the least use,get(1) and return -1,get(2) and return 1.

      Example 2:

      Input:
      LRUCache(1)
      set(2, 1)
      get(2)
      set(3, 2)
      get(2)
      get(3)
      Output:[1,-1,2]
      Explanation:
      cache cap is 1,set(2,1),get(2) and return 1,set(3,2) and delete (2,1),get(2) and return -1,get(3) and return 2.
      class LRUCache:
          """
          @param: capacity: An integer
          """
          def __init__(self, capacity):
              # do intialization if necessary
              self.cap = capacity
              self.disklist ={}
              self.timelist =[]
          """
          @param: key: An integer
          @return: An integer
          """
          def get(self, key):
              # write your code here
              temp = self.disklist.get(key)
              if temp:
                  self.timelist.remove(key)
                  self.timelist.append(key)
                  return self.disklist[key]
              else:
                  return -1
          """
          @param: key: An integer
          @param: value: An integer
          @return: nothing
          """
          def set(self, key, value):
              # write your code here
              temp = self.disklist.get(key)
              if temp:
                  self.disklist[key] = value
                  self.timelist.remove(key)
                  self.timelist.append(key)
              elif len(self.disklist) < self.cap:
                  self.disklist[key]=value
                  self.timelist.append(key)
              else:
                  temp=self.timelist.pop(0)
                  self.disklist.pop(temp)
                  self.disklist[key]=value
                  self.timelist.append(key)

              

      纽约州·法拉盛
    • 0
    • 0
    • 0
    • 411
    • 请登录之后再进行评论

      登录
    • 做任务