Leetcode題解 Python & C#：四月挑戰DAY24 LRU Cache

編寫一個 cache ，採取  Least recent used的方式替換已滿cache。

這道題目，有一個關鍵特點，就是會依照最近的使用次序來決定哪一個要在已滿的情形被先換掉。

所以，要有個能紀錄使用次序的方式。

如果某鍵被使用到，那就把它挪到最後方；如果需要替換，就先刪除第一個鍵。

還要有個記錄對應值的 hashtable ，如果使用 get() ，才能從其中撈出值來。

要實現這樣的功能，python有 OrderedDict 類別可以使用（from collections import OrderedDict)，這是我覺得最快速的方式。

即使不用，用 dict 與 list 也能做出一樣的機制，只是慢上許多。

不然還有一種方式，使用 linkedlist 做出來，因為只要改變指向，所以會比起用 list 刪改還快上不少。


Python

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.cachelist = []

    def get(self, key: int) -> int:
        if key in self.cache:
            self.cachelist.remove(key)
            self.cachelist.append(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:            
            self.cachelist.remove(key)
        elif len(self.cachelist) == self.capacity:
            del self.cache[self.cachelist[0]]
            del self.cachelist[0]
        self.cache[key] = value
        self.cachelist.append(key)

C#

public class LRUCache {
    public int cap;
    public Dictionary cache = new Dictionary();
    public List cachelist = new List();
    
    public LRUCache(int capacity) {
        cap = capacity;
    }
    
    public int Get(int key) {
        if (cache.ContainsKey(key))
        {
            cachelist.Remove(key);
            cachelist.Add(key);
            return cache[key];
        }
        else
        {
            return -1;
        }
    }
    
    public void Put(int key, int value) {
        if(cache.ContainsKey(key))
        {
            cachelist.Remove(key);
        }
        else if(cachelist.Count == cap)
        {
            cache.Remove(cachelist[0]);
            cachelist.Remove(cachelist[0]);
        }
        cachelist.Add(key);
        cache[key] = value;

    }
}