LRU 캐 시 메커니즘 (LeetCode 146 번) 자바 구현

제목 설명
당신 이 파악 한 데이터 구 조 를 활용 하여 하 나 를 설계 하고 실현 하 세 요. 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

2. 문제 풀이 사고
두 개의 데이터 구 조 를 이용 하면 둘 을 결합 하면 효 과 를 실현 할 수 있다.코드 를 직접 보시 면 됩 니 다.
1. 최근 사용 횟수 를 저장 하 는 데 사 용 됩 니 다. (저 는 스 택 을 사 용 했 고 다른 데이터 구 조 를 사용 할 수 있 습 니 다)
2. 데 이 터 를 저장 하 는 데 사용 되 는 것 은 get 을 얻 고 get 에 저장 하 는 데 편리 합 니 다. (여기 서 hashmap 을 사 용 했 습 니 다)
3. 자바 코드 실행 가능

class LRUCache {

    Stack stack;
    Map map;
    int size;
    
    public LRUCache(int capacity) {
        stack = new Stack<>();
        map = new HashMap<>();
        size = capacity;
    }
    
    public int get(int key) {
        if(!stack.contains(key)){
            return -1;
        }
        stack.remove(Integer.valueOf(key));
        stack.push(key);
        return map.get(key);
    }
    
    public void put(int key, int value) {
        if(stack.contains(key)){
           stack.remove(Integer.valueOf(key)); 
        }else{
            if(stack.size() == size){
                int count = stack.remove(0);
                map.remove(count);
            }
        }
        stack.push(key);
        map.put(key, value);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

LRU 캐 시 메커니즘 (LeetCode 146 번) 자바 구현

LRU (최근 최소 사용) 캐 시 메커니즘.다음 동작 을 지원 해 야 합 니 다: 데이터 가 져 오기 get 기록 데이터 put 。 데이터 가 져 오기 get(key) - 키 (key) 가 캐 시 에 존재...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

LRU 캐 시 메커니즘 (LeetCode 146 번) 자바 구현

좋은 웹페이지 즐겨찾기