LeetCode - python 146. LRU 캐 시 메커니즘

1815 단어
제목 링크 난이도: 중간      형식: 해시 테이블
당신 이 파악 한 데이터 구 조 를 활용 하여 LRU (최근 최소 사용) 캐 시 체 제 를 설계 하고 실현 합 니 다.데이터 get 을 가 져 오고 데 이 터 를 기록 하 는 put 를 지원 해 야 합 니 다.
데이터 get (key) 가 져 오기 - 키 (key) 가 캐 시 에 존재 하면 키 의 값 (항상 정수) 을 가 져 옵 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.데이터 put (key, value) 를 기록 합 니 다. - 키 가 존재 하지 않 으 면 데이터 값 을 기록 합 니 다.캐 시 용량 이 상한 선 에 이 르 렀 을 때 새 데 이 터 를 쓰기 전에 최근 에 가장 적 게 사용 한 데이터 값 을 삭제 하여 새로운 데이터 값 에 공간 을 남 겨 야 합 니 다.
진급:
당신 은 O (1) 시간 복잡 도 내 에 이 두 가지 조작 을 완성 할 수 있 습 니까?
예시
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); /돌아오다
문제 풀이 의 사고 방향.
해시 표 의 저장 소 는 무질서 합 니 다. OrderedDict () 를 사용 하면 질서 있 게 저장 할 수 있 습 니 다. 저 장 된 순 서 는 사전 에 들 어 가 는 순서에 따라 pop (key) 을 통 해 key 에 대응 하 는 value popite () 를 얻 을 수 있 고 마지막 으로 들 어 가 는 value 를 얻 을 수 있 습 니 다. popitem (last = False) 은 첫 번 째 표 의 value 를 얻 을 수 있 습 니 다.
코드 구현
import collections
class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity         
        self.catch = collections.OrderedDict()
        

    def get(self, key: int) -> int:
        if key not in self.catch:
            return -1
       
        value = self.catch.pop(key)
        self.catch[key] = value
        return value

    def put(self, key: int, value: int) -> None:
        if key in self.catch:
            self.catch.pop(key)
        elif self.catch and self.capacity == 0:
            self.catch.popitem(last=False)
        else:
            self.capacity -= 1
        self.catch[key] = value 

본문 링크:https://www.jianshu.com/p/77d14cf02196

좋은 웹페이지 즐겨찾기