LeetCode-Python-146. LRUキャッシュメカニズム
あなたが把握しているデータ構造を運用し、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)の操作の複雑さを表すハッシュテーブル.
取得データ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