常见数据结构设计

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;
    }
}

PreviousMatrix Inplace Operations Next(G) Design / OOD 类算法题

Last updated 3 years ago