LeetCode-Python-146. LRUキャッシュメカニズム

1835 ワード

あなたが把握しているデータ構造を運用し、LRU(最近最も少ない使用)キャッシュメカニズムを設計し、実現します.データgetの取得とデータputの書き込みをサポートする必要があります.
取得データget(key)-キー(key)がキャッシュに存在する場合、キーの値(常に正数)が取得され、そうでない場合は-1が返されます.書き込みデータput(key,value)-鍵が存在しない場合、そのデータ値が書き込まれます.キャッシュ容量が上限に達した場合、新しいデータを書き込む前に、最近最も少ないデータ値を削除して、新しいデータ値にスペースを残す必要があります.
ステップ:
O(1)時間の複雑さの中でこの2つの操作を完了できますか?
例:
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
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/lru-cache著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:
O(1)の操作の複雑さを表すハッシュテーブル.
 
from collections import OrderedDict
class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.record = OrderedDict()
        self.capacity = capacity
        
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        # print self.record
        if key in self.record: #    
            tmp = self.record.pop(key)
            self.record[key] = tmp #      key
            return self.record[key]
        else:
            return -1
        

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.record: #  key    
            self.record.pop(key)
        else:
            if self.capacity > 0: #    
                self.capacity -= 1
            else: #    ,        
                self.record.popitem(last = False)
        self.record[key] = value