常见数据结构

LRU Cache

非常经典的一道题，很考察设计能力，以及data structure的选用问题

一句话描述这题的话，就是一个 “头 + 尾 dummy node 的双向链表” + “HashMap”.

• 先沟通各种 input/output
• 思考流程
• 把流程用 comments (另一种颜色 mark 笔写下来)
• 把发现流程中重复率高的地方写成 function
• 模块化填充，改错。

public class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

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

    private HashMap<Integer, Node> map = new HashMap<>();
    // least used node
    private Node dummyHead = new Node(-1, -1);
    // most used node
    private Node dummyTail = new Node(-1, -1);
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        Node cur = map.get(key);

        // move the node to tail
        if (cur.next != dummyTail) {
            // disjoint from linkedlist
            cur.next.prev = cur.prev;
            cur.prev.next = cur.next;
            moveToTail(cur);
        }

        return cur.value;
    }

    public void moveToTail(Node node) {
        // connect four pointer
        node.next = dummyTail;
        node.prev = dummyTail.prev;
        node.prev.next = node;
        dummyTail.prev = node;
    }

    public void set(int key, int value) {
        // have to update hashmap
        if (get(key) != -1) {
            map.get(key).value = value;
            return;
        }

        // before add new node, need to check the capacity
        if (map.size() == capacity) {
            // remove first
            dummyHead.next = dummyHead.next.next;
            dummyHead.next.prev = dummyHead;
            // update map
            map.remove(key);
        }

        Node newNode = new Node(key, value);
        moveToTail(newNode);
        // update hashmap
        map.put(key, newNode);
    }

}

Sliding Window Maximum

这道题的暴力解法是O(nk),用两个指针维护一个window，然后每次迭代去寻找window里面最大的数。

如何优化到O(n)?

因为我们只关心max，所以维护一个数据结构，

• 可以维护插入的顺序，方便的移除已经不在window之内的数。
• 同时每次add一个数之前把小于它的数都pop掉，让在这个数据结构里面的数呈现单调性。
• 由于每一个元素只会被 add 和 remove 一次，整个流程的均摊复杂度就是 O(1).

因此我们可以用deque来实现，从尾端加入新数，把小于新数的数都pop掉，从头端去看max。因为我们维持了插入的顺序，所以头端的数是window的第一个数。

Deque 里面要存 index，而不是值。这样可以方便移除不在window里面的数。

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new LinkedList<>();
    int n = nums.length;
    int[] result = new int[n - k + 1];

    for(int i = 0; i < n; i++) {
        // remove shift-out element
        if(!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }

        // remove ints smaller than shift-in int
        while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
            deque.pollLast();
        }

        // add new one
        deque.offerLast(i);

        // when the window has formed
        if(i >= k - 1) {
            result[i + 1- k] = nums[deque.peekFirst()];
        }
    }

    return result;
}