LeetCode - Algorithms - [Mid] 146. LRU 캐 시 메커니즘

당신 이 파악 한 데이터 구 조 를 활용 하여 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); /돌아오다
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/lru-cache 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
이 문제 의 사상 은 사실 매우 그립다.
우선 O (1) 가 필요 하 다 면 HashMap 이 있 을 수 밖 에 없다. 그렇다면 문 제 는 LRU 를 어떻게 실현 하 느 냐 하 는 것 이다.무엇 을 함께 사용 하면 가장 오래 사용 하지 않 은 것 을 제거 하고 고정 상한 선 이 있 으 며 자 연 스 럽 게 선형 데이터 구 조 를 생각 할 수 있 습 니까?
그러면 '대기 열' 의 구 조 를 생각 한 다음 에 자 유 롭 게 삽입 하고 머리 끝 에 추가 하 는 방법 을 고려 할 수 있다. 그러면 링크 의 '대기 열' 구조 일 수 밖 에 없다.
그러면 HashMap 은 링크 의 무 작위 접근 을 실현 하고 링크 는 LRU 를 실현 합 니 다.
그리고 코드 를 쓸 때 무엇 을 주의해 야 합 니까?여기 서 우 리 는 자신 이 양 방향 링크 를 쓰 는 형식 을 사용한다. 그러면 실현 할 때 가장 중요 한 점 이 있다.
위 두부 결점 과 위 꼬리 결점 을 사용 해 야 한다.

    class LRUCache {

        private HashMap<Integer, LinkList> listMap;

        private LinkList head;
        private LinkList tail;

        private int maxSize;

        private int NOT_FOUND_NUM = -1;

        public LRUCache(int capacity) {
            listMap = new HashMap<>();

            head = new LinkList(NOT_FOUND_NUM, NOT_FOUND_NUM);
            tail = new LinkList(NOT_FOUND_NUM, NOT_FOUND_NUM);
            head.post = tail;
            tail.pre = head;

            maxSize = capacity;
        }

        public int get(int key) {
            if (!listMap.containsKey(key)) {
                return NOT_FOUND_NUM;
            }
            LinkList current = listMap.get(key);
            moveToHead(current);
            return current.value;
        }

        public void put(int key, int value) {
            if (listMap.containsKey(key)) {
                LinkList current = listMap.get(key);
                moveToHead(current);
                current.value = value;
                return;
            }
            LinkList current = new LinkList(key, value);
            addToHead(current);
            listMap.put(key, current);
            if (listMap.size() > maxSize) {
                int tailKey = getTailKey();
                listMap.remove(tailKey);
                removeTail();
            }
        }

        private int getTailKey() {
            LinkList tailList = tail.pre;
            return tailList.key;
        }

        private void removeTail() {
            LinkList tailList = tail.pre;
            removeList(tailList);
        }

        private void moveToHead(LinkList list) {
            removeList(list);
            addToHead(list);
        }

        private void addToHead(LinkList list) {
            LinkList next = head.post;

            head.post = list;
            list.pre = head;

            list.post = next;
            next.pre = list;
        }

        private void removeList(LinkList list) {
            LinkList pre = list.pre;
            LinkList post = list.post;
            pre.post = post;
            post.pre = pre;
        }
    }

    class LinkList {
        int key;
        int value;
        LinkList pre;
        LinkList post;

        public LinkList(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }