LeetCode 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);       //     4

분석:
1. 스 택 과 hashmap 을 사용 하여: (효율 이 높 지 않 음)
get：
hashmap 에 있 으 면 스 택 에 가서 해당 하 는 노드 를 스 택 꼭대기 에 놓 으 세 요. 그러면 스 택 지붕 은 최근 에 가장 자주 사용 하 는 것 입 니 다.hashmap 에 없 으 면 - 1 로 돌아 갑 니 다.
 put：
hashmap 에 이 key 값 이 있 으 면 value 의 값 을 업데이트 하고 스 택 에서 요 소 를 찾 아 스 택 꼭대기 에 놓 습 니 다.
hashmap 에 이 key 값 이 없 으 면 hashmap 의 요소 갯 수 (size) 와 설 정 된 캐 시 capacity 를 비교 합 니 다.
       （1）size
       (2) 그렇지 않 으 면 용량 이 부족 합 니 다. 스 택 베이스 요소 (최근 에 사용 되 지 않 은) 를 삭제 하고 이 요 소 를 hashmap 에서 도 삭제 합 니 다.그리고 새로운 요 소 를 hashmap 에 넣 고 새로운 요 소 를 스 택 꼭대기 에 놓 습 니 다.
2. 양 방향 링크 와 hashmap 사용: (효율 이 높 음)
스 택 의 바 텀 저장 소 는 하나의 배열 을 유지 하고 삭제 작업 을 할 때 전체 배열 이 흔 들 리 며 링크 를 사용 할 때 포인터 방향 만 바 꾸 면 효율 이 더욱 높다.
방법 1 과 차이 가 많 지 않 습 니 다. 스 택 지붕 은 링크 의 헤드 포인터 (자주 사용) 로 바 뀌 었 고 스 택 바닥 은 링크 의 꼬리 포인터 (자주 사용 하지 않 음) 로 바 뀌 었 습 니 다.
get：
만약 에 hashmap 에 있 으 면 링크 에서 해당 하 는 노드 를 링크 머리 에 넣 으 면 링크 머리 는 최근 에 가장 자주 사용 하 는 것 이다.hashmap 에서 찾 지 못 하면 - 1 로 돌아 갑 니 다.
 put：
hashmap 에 이 key 값 이 있 으 면 value 의 값 을 업데이트 하고 링크 에서 요 소 를 찾 아 링크 머리 에 넣 습 니 다.
hashmap 에 이 key 값 이 없 으 면 hashmap 의 요소 갯 수 (size) 와 설 정 된 캐 시 capacity 를 비교 합 니 다.
       （1）size
       (2) 그렇지 않 으 면 용량 이 부족 합 니 다. 체인 꼬리 요 소 를 삭제 하고 이 요 소 를 hashmap 에서 도 삭제 합 니 다.그리고 새로운 요 소 를 hashmap 에 넣 고 새로운 요 소 를 링크 머리 에 넣 습 니 다.
Java 구현:
주: 양 방향 링크 의 머리 와 꼬리 노드 는 모두 빈 노드 를 사용 합 니 다.진정한 데이터 노드 는 이 두 노드 를 제거 하 는 것 이다.

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @ClassName:LURCache
 * @description:
 * @Author: why
 * @Date: 2019/4/20
 */
public class LRUCache {
    private class Node {
        private int key;
        private int value;

        private Node pre = null;
        private Node next = null;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        Node() {
        }

    }

    private Map map;

    //    
    private int capacity;

    private Node tail = new Node();

    private Node head = new Node();

    //    
    private int size;

    LinkedList

    LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        size = 0;
        head.next = tail;
        tail.pre = head;
    }

    public void deleteNode(Node node) {
        Node preNode = node.pre;
        Node nextNode = node.next;

        preNode.next = nextNode;
        nextNode.pre = preNode;

        node.pre = null;
        node.next = null;
    }

    public void addNode(Node node) {
        Node headNext = head.next;

        head.next = node;
        headNext.pre = node;

        node.pre = head;
        node.next = headNext;
    }

    public void put(int key, int value) {

        Node node = map.get(key);

        if (node != null) {

            node.value = value;

            deleteNode(node);

            addNode(node);

        } else {

            node = new Node(key, value);

            if (size < capacity) {
                size++;
            } else {
                //    （      ），map   ！！
                map.remove(tail.pre.key);
                deleteNode(tail.pre);
            }

            //    ，   map！！！
            addNode(node);
            map.put(key, node);
        }
    }

    public int get(int key) {
        Node node = map.get(key);

        if (node == null) {

            return -1;
        }
        deleteNode(node);

        addNode(node);

        return node.value;

    }
    
}

테스트:
18 / 18 테스트 용례
상태: 통과
실행 시간: 142 ms
제출 시간: 0 분 전