常见数据结构设计

LRU Cache

一道非常亲切熟悉的题，当初刷 lintcode 的时候非常喜欢这道。这道题因为细节很多，但是操作重复性高，所以非常适合先把流程写下来，然后用 helper 函数实现。

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

• 先沟通各种 input/output

• 思考流程

• 把流程用 comments (另一种颜色 mark 笔写下来)

• 把发现流程中重复率高的地方写成 function

• 模块化填充，改错。

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

    private int capacity;
    private HashMap<Integer, Node> map;
    // Head : Most recently used
    private Node dummyHead;
    // Tail : Least recently used
    private Node dummyTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<Integer, Node>();
        dummyHead = new Node(-1,-1);
        dummyTail = new Node(-1,-1);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

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

        // Get current node
        Node node = map.get(key);
        // Disconnect it from the linkedlist
        node.prev.next = node.next;
        node.next.prev = node.prev;
        // Move it to the front
        moveToFront(node);
        // Return value
        return node.value;
    }

    public void set(int key, int value) {
        if(map.containsKey(key)){
            // Get current node
            Node node = map.get(key);
            // Disconnect it from the linkedlist
            node.prev.next = node.next;
            node.next.prev = node.prev;
            // Move it to the front
            moveToFront(node);
            // set value
            node.value = value;
        } else {
            if(map.size() >= capacity){
                // Remove LRU element and its key
                removeLRU();
            }
            // Create new node
            Node node = new Node(key, value);
            // Save its key in map
            map.put(key, node);
            // Move it to the front
            moveToFront(node);
        }
    }

    private void moveToFront(Node node){
        Node oldHead = dummyHead.next;

        // Connect node to dummyHead
        dummyHead.next = node;
        node.prev = dummyHead;

        // Connect node to oldHead
        node.next = oldHead;
        oldHead.prev = node;
    }

    private void removeLRU(){
        Node node = dummyTail.prev;
        // Disconnect node from linkedlist
        node.prev.next = node.next;
        node.next.prev = node.prev;
        // Set null of its pointers
        node.next = null;
        node.prev = null;
        // Remove its key from hashmap
        map.remove(node.key);
    }
}

Find Median from Data Stream

也是非常经典的题。

• new PriorityQueue<>(Collections.reverseOrder());

• 把所有数字分成两个区间，一个区间为 <= median 的，存在 maxHeap 里；另一个为 >= median 的，存在 minHeap 里，这样我们每次在堆顶看到的都是 median candidates.

• 因此在插入新元素的时候，如果发现其 <= maxHeap top，则说明它位于左区间，插入 max; 反之则插入 minHeap 所代表的右区间。

• 每次新元素插入之后要保持平衡，堆顶的元素切换其实代表着区间分界线的转移。

public class MedianFinder {
    // max heap stores all elements smaller / equal to median
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
    // min heap stores all elements bigger / equal to median
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

    // Adds a number into the data structure.
    public void addNum(int num) {
        // Check heap top

        if(maxHeap.size() == 0 || num <= maxHeap.peek()){
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }

        // min/max heap's size would not differ more than one
        // Rebalance if necessary
        while(Math.abs(maxHeap.size() - minHeap.size()) > 1){
            if(maxHeap.size() > minHeap.size()){
                minHeap.offer(maxHeap.poll());
            } else {
                maxHeap.offer(minHeap.poll());
            }
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        int maxSize = maxHeap.size();
        int minSize = minHeap.size();

        if(maxSize == minSize) return (double) (maxHeap.peek() + minHeap.peek()) / 2;
        if(maxSize - 1 == minSize) return (double) maxHeap.peek();
        if(maxSize == minSize - 1) return (double) minHeap.peek();

        return 0;
    }
};

Sliding Window Maximum

操作特点：

• 只关心区域内的 max;

• 只要同一区域内 max 一样，输出就一样，不在意元素的出现顺序，因此这题有别于 max/min stack 的保存元素顺序要求。

这题暴力循环可以 O(nk)，hasheap 可以 O(n log k)，deque 可以 O(n).

我们每一步要执行下面三个操作：

• 添加当前元素 nums[i];

• 删除指定元素 nums[i - k];

• 找到当前 window max;

暴力解法中，我们可以直接维护一个 list，每次操作都进行扫描，这样的复杂度是：

• Add O(1)

• Remove O(k)

• max O(k)

另一种选择是，维护一个 sorted list，这样的复杂度是：

• Add O(k)

• Remove O(k)

• max O(1)

再观察题目特性可以发现，我们在维护 sorted list 上有很多可以取巧的地方：

• 因为我们只关心每个 window 上的 max，因此没有必要把 window 内的所有元素都留着，在 Add 的时候可以直接把小于新元素的值都 pop 掉；

• 而在 remove 上，对最终结果会产生影响的，只有我们 remove 的元素就是 max 的情形，因为其他无关元素在 add 的时候就被拿掉了；因此我们可以存一个元素的相对位置，以此来判断我们要删掉的元素是不是当前的 max.

• 因为我们维护的是 sorted array ，max 依然是 O(1).

• 由于每一个元素只会被 add 和 remove 一次，整个流程的均摊复杂度就是 O(1).

要点：

• 维护一个可以双向操作的 sorted array.

• Deque 里面要存 index，而不是值，不然会出现 [8,1,2,8...] 这种情况下，我们有可能会把刚加进去的 8 又给拿出来的 bug.

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];

        int[] rst = new int[nums.length - k + 1];
        // Deque stores indexes of elements i, in descending order of nums[i]
        // First : smallet element in current window
        // Last : biggest element in current window
        Deque<Integer> deque = new LinkedList<>();

        for(int i = 0; i < nums.length; i++){
            while(!deque.isEmpty() && nums[i] > nums[deque.peekFirst()]){
                deque.pollFirst();
            }
            deque.offerFirst(i);
            // element to remove from sliding window
            if(i - k == deque.peekLast()) deque.pollLast();
            if(i - k + 1 >= 0) rst[i - k + 1] = nums[deque.peekLast()];
        }

        return rst;
    }
}