[LeetCode][python3]Day24. LRU Cache (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.24

1. My solution

class LRUCache: 
    capacity=0
    cache={}
    use=[]
    def __init__(self, capacity: int):
        self.capacity=capacity
        self.cache={}
        self.use=[]
        
    def get(self, key: int) -> int:
        if key in self.cache:
            self.use.remove(key)
            self.use.append(key)
            return self.cache[key]
        else:
            return -1
        
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key]=value
            self.use.remove(key)
            self.use.append(key)
            return
        elif len(self.cache)<self.capacity:
            self.cache[key]=value
            self.use.append(key)
            return
        else:
            del self.cache[self.use[0]]
            del self.use[0]
            self.cache[key]=value
            self.use.append(key)
            return

Explanation:

This solution uses an array use to record the sequence of the recently use item. Which the main idea is shown in the pic below.

2. A better Solution

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
        
    def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)
        return self.cache.get(key, -1)
        
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        else:
            if(len(self.cache) >= self.capacity):
                self.cache.popitem(last=False)
        self.cache[key] = value

Note:

• from collections import OrderedDict Import OrderedDict package
• OrderedDict.move_to_end(key,last=True) Move the key object to the end of list, if last==False then move the key object to the front.
• OrderedDict.popitem(last=True) Pop the last item if last==True, or pop the first item when last==False

from collections import OrderedDict
print('Example of OrderedDict:')
d1=OrderedDict()
d1['a']='A'
d1['b']='B'
d1['c']='C'
 
d2=OrderedDict()
d2['c']='C'
d2['a']='A'
d2['b']='B'
 
print(d1==d2)
  #>>False
d2.move_to_end('c')
print(d1==d2)
  #>>True

Explanation:

The solution use OrderedDict to implement the idea in the first solution.