力扣HOT100解题记录p2

146. LRU 缓存

class LRUCache {
    class Node {
        Node prev;
        Node next;
        int key;
        int value;
        public Node(){}
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    Map cache = new HashMap<>();
    int size;
    int capacity;
    Node head;
    Node tail;

    public LRUCache(int capacity) {
        size = 0;
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        head.prev = tail;
        tail.next = head;
        tail.prev = head;
    };
    
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null){
            return -1;
        }
        remove(node);
        moveToHead(node);
        return node.value;
    }

    
    public void put(int key, int value) {
        if (cache.containsKey(key)){
            Node node = cache.get(key);
            node.value = value;
            remove(node);
            moveToHead(node);
            return;
        }
        Node node = new Node(key, value);
        cache.put(key,node);
        moveToHead(node);
        size++;
        if (size > capacity){
            cache.remove(tail.prev.key);
            remove(tail.prev);
            size--;
        }
    }

    public void remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void moveToHead(Node node){
        head.next.prev = node;
        node.next = head.next;
        node.prev = head;
        head.next = node;
    }
}

/**
 * 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);
 */

记忆知识点与分析：
背就好了

155 最小栈

class MinStack {
        Deque normalStack;
        Deque minStack;

    public MinStack() {
        normalStack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.addLast(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        normalStack.addLast(val);
        minStack.addLast(Math.min(minStack.peekLast(), val));
    }
    
    public void pop() {
        normalStack.removeLast();
        minStack.removeLast();
    }
    
    public int top() {
        return normalStack.peekLast();
    }
    
    public int getMin() {
        return minStack.peekLast();
    }
}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

记忆知识点与分析：
一日三顿饭。。。。