LeetCode 146 LRUキャッシュメカニズムpython

タイトルの説明
あなたが把握しているデータ構造を運用し、LRU(最近最も少ない使用)キャッシュメカニズムを設計し、実現します.データgetの取得とデータputの書き込みをサポートする必要があります.
取得データget(key)-キー(key)がキャッシュに存在する場合、キーの値(常に正数)が取得され、そうでない場合は-1が返されます.書き込みデータput(key,value)-鍵が存在しない場合、そのデータ値が書き込まれます.キャッシュ容量が上限に達した場合、新しいデータを書き込む前に、最近最も少ないデータ値を削除して、新しいデータ値にスペースを残す必要があります.
サンプル

LRUCache cache = new LRUCache( 2 /*      */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       //     1
cache.put(3, 3);    //          2   
cache.get(2);       //    -1 (   )
cache.put(4, 4);    //          1   
cache.get(1);       //    -1 (   )
cache.get(3);       //     3
cache.get(4);       //     4

アイデア1:辞書記録鍵と値の関係を用いてキュー記録鍵の使用前後を用いて最近の最小使用量を決定する

class LRUCache:

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.maxlength = capacity
        self.array = {}
        self.array_list = []

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        value = self.array.get(key)
        #                 
        if value is not None and self.array_list[0] is not key:
            index = self.array_list.index(key)
            self.array_list.pop(index)
            self.array_list.insert(0, key)

        value = value if value is not None else -1
        return value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        #     
        if self.array.get(key) is not None:
            index = self.array_list.index(key)
            self.array.pop(key)
            self.array_list.pop(index)

        #     
        if len(self.array_list) >= self.maxlength:
            key_t = self.array_list.pop(self.maxlength-1)
            self.array.pop(key_t)

        #     
        self.array[key] = value
        self.array_list.insert(0, key)

アイデア2:別の方法はcollectionsのOrderedDictを使用してちょうどcollectionsに既存のソート辞書を使用して、特にpopitemという方法を使用してLRU機能を実現することができます.

from collections import OrderedDict


class LRUCache:

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.dic = OrderedDict()

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.dic:
            val = self.dic[key]
            del self.dic[key]
            self.dic[key] = val
            return val
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.dic:
            del self.dic[key]
        elif len(self.dic) == self.capacity:
            # popitem     True           False       
            self.dic.popitem(False)
        self.dic[key] = value

最後に
ブラシしたLeetCodeのソースコードをGithubに置いて、好きな友达や役に立つと思っている友达にstarやfollowを注文してほしいです.以下のコメントや私信や連絡先で私を探すことができます.連絡先QQ:791034063 Wechat:liuyuhang 791034063 CSDN:https://blog.csdn.net/Sun_White_Boy Github:https://github.com/liuyuhang791034063