LeetCode 문제 풀이 디자인 문제 (지속 업데이트)

1. LRU 캐 시 메커니즘
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

/*
  ：
  Map+Stack
 */
public class LRUCache {
    Map map;
    Stack stack;
    int size;

    public LRUCache(int capacity) {
        stack = new Stack<>();
        map = new HashMap<>(capacity);
        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);
    }
}

2. 가장 작은 창고
최 소 잔
push, pop, top 작업 을 지원 하고 상수 시간 내 에 최소 요 소 를 검색 할 수 있 는 스 택 을 설계 합 니 다.

push(x) -- 원소 x 를 창고 에 밀어 넣 습 니 다.

pop() -- 창고 꼭대기 의 요 소 를 삭제 합 니 다.

top() -- 창고 꼭대기 요 소 를 가 져 옵 니 다.

getMin () - 검색 창고 의 최소 요소 입 니 다.

  :

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   -->    -3.
minStack.pop();
minStack.top();      -->    0.
minStack.getMin();   -->    -2.

/*
  ：
     ：        ；          ，               
 */
public class MinStack {
    private Stack pStack;
    private Stack mStack;

    public MinStack() {
        pStack = new Stack<>();
        mStack = new Stack<>();
    }

    public void push(int x) {
        pStack.push(x);
        if (mStack.isEmpty() || mStack.peek() >= x) {
            mStack.push(x);
        }
    }

    public void pop() {
        int x = pStack.pop();
        if (x == mStack.peek()) mStack.pop();
    }

    public int top() {
        return pStack.peek();
    }

    public int getMin() {
        return mStack.peek();
    }

}