(G)数据结构

LRU Cache

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

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

• 先沟通各种 input/output

• 思考流程

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

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

• 模块化填充，改错。

public class LRUCache {

    class Node{
        int key; int value;
        Node pre; Node next;
        public Node(int key, int value){
            this.key = key; 
            this.value = value;
        }
    }
    Node head = null; Node tail = null; int capacity;
    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        Node n = map.get(key);
        remove(n);
        addToHead(n);
        return n.value;
    }

    public void addToHead(Node n){
        n.next = head;
        n.pre = null;
        if(head!=null)
            head.pre = n;
        head = n;
        if(tail==null)
            tail = head;
    }

    public void remove(Node node){
        if(node.pre!=null){
            node.pre.next=node.next;
        }
        else
            head = node.next;
        if(node.next!=null){
            node.next.pre = node.pre;
        }
        else
            tail = node.pre;
    }

    public void put(int key, int value) {
        if(!map.containsKey(key)){
            Node newNode = new Node(key, value);
            if(map.size()>=capacity){
                map.remove(tail.key);
                remove(tail);
            }
            addToHead(newNode);
            map.put(key, newNode);
        }
        else{
            Node pre = map.get(key);
            pre.value=value;
            remove(pre);
            addToHead(pre);
        }
    }
}

LFU Cache

这道题和LRU cache很像, 不一样的是要基于count来删除元素, 当count一样时, 再根据recent used原则删除. 所以必须建立以count为索引的删除方式, hashmap<count, LinkedHashSet<key>> 来存储. 同时需要一个map来维护(key, count). 想到这里, 这个问题基本就解决了.

public class LFUCache {

    int capacity;
    int min=1;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); //key:value
    HashMap<Integer, Integer> count = new HashMap<Integer, Integer>(); //key:count
    HashMap<Integer, LinkedHashSet<Integer>> list = new HashMap<Integer, LinkedHashSet<Integer>>();

    public LFUCache(int capacity) {
        this.capacity = capacity;
        list.put(1, new LinkedHashSet<Integer>());
    }

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

        if(count.get(key)==min && list.get(min).size()==1)
            min++;

        list.get(count.get(key)).remove(key);
        count.put(key, count.get(key)+1);
        if(!list.containsKey(count.get(key))){
            list.put(count.get(key), new LinkedHashSet<Integer>());
        }
        list.get(count.get(key)).add(key);

        return map.get(key);
    }

    public void remove(){
        int key = list.get(min).iterator().next();
        list.get(min).remove(key);
        count.remove(key);
        map.remove(key);
    }

    public void put(int key, int value) {
        if(capacity<=0) return;

        if(!map.containsKey(key)){
            if(map.size()==capacity)
                remove();
            map.put(key, value);
            count.put(key, 1);
            list.get(1).add(key);
            min = 1;
        }
        else{
            map.put(key, value);
            get(key);
        }
    }
}

Find Median from Data Stream

也是非常经典的题。+

• new PriorityQueue<> (Collections.reverseOrder());
• 把所有数字分成两个区间，一个区间为 <= median 的，存在 maxHeap 里；另一个为 >= median 的，存在 minHeap 里，这样我们每次在堆顶看到的都是 median candidates.
• 因此在插入新元素的时候，如果发现其 <= maxHeap top，则说明它位于左区间，插入 max; 反之则插入 minHeap 所代表的右区间。
• 每次新元素插入之后要保持平衡，堆顶的元素切换其实代表着区间分界线的转移。

自己写的很精简的写法, 每次来的新数字先加入小数大顶堆, 保证大数小顶堆的size总比小数大顶堆的size大一. 同时保证大数小顶堆的peek比小数大顶堆的peek要大.

public class MedianFinder {

    /** initialize your data structure here. */
    PriorityQueue<Integer> small = new PriorityQueue<Integer>(Collections.reverseOrder());
    PriorityQueue<Integer> large = new PriorityQueue<Integer>();
    public MedianFinder() {

    }

    public void addNum(int num) {
        small.add(num);
        if(small.size()>large.size()){
            large.add(small.poll());
        }
        if(!large.isEmpty() && !small.isEmpty() && large.peek()<small.peek()){
            small.add(large.poll());
            large.add(small.poll());
        }
    }

    public double findMedian() {
        if(large.size()==small.size()){
            return (large.peek()+small.peek())/2.0;
        }
        else if(large.size()>small.size())
            return (double)large.peek();
        return 0.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. 单调递减的, peek永远是当前最大元素的index.

• 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];

        LinkedList<Integer> deque = new LinkedList<Integer>();
        int[] res = new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            if(!deque.isEmpty() && deque.peekFirst() == i-k)
                deque.poll();

            while(!deque.isEmpty() && nums[deque.peekLast()]<nums[i])
                deque.removeLast();

            deque.offer(i);

            if(i+1>=k){
                res[i+1-k] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}

这里我自己的写法是通过hashmap来存需要移除的数字, 当priorityqueue的top元素是hashmap中存在的, 则需要移除. 开始用了hashset, 这里忽略了可能存在重复数字, 比如[8,0,0, 8], 用hashset会将两个8都移除.

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        int[] ans = new int[nums.length-k+1];
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int right=0;
        for(;right<k-1;right++) pq.offer(nums[right]);

        for(int left=0;right<nums.length;right++, left++){
            pq.offer(nums[right]);
            ans[left] = pq.peek();
            map.put(nums[left], map.getOrDefault(nums[left], 0)+1);
            while(map.containsKey(pq.peek()) && map.get(pq.peek())>0){
                map.put(pq.peek(), map.get(pq.peek())-1);
                pq.poll();
            }
        }
        return ans;
    }
}