摘要：首先要做到是，能想到的數(shù)據(jù)結(jié)構(gòu)只有兩三種，一個(gè)是，一個(gè)是，是，還有一個(gè)，是。不太可能，因?yàn)殚L(zhǎng)度要而且不可變，題目也沒(méi)說(shuō)長(zhǎng)度固定?？梢宰龅胶投际恰Ｒ?yàn)檫€有函數(shù)，要可以，所以還需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄順序，自然想到。

題目鏈接：https://leetcode.com/problems...

這個(gè)題要求O(1)的復(fù)雜度。首先要做到get(key)是O(1)，能想到的數(shù)據(jù)結(jié)構(gòu)只有兩三種，一個(gè)是HashMap，一個(gè)是List，key是index，還有一個(gè)Array[value]， key是index。array不太可能，因?yàn)殚L(zhǎng)度要initial而且不可變，題目也沒(méi)說(shuō)長(zhǎng)度固定。list也不行，因?yàn)橛衟ut操作，list的insert操作是O(N)的。hashmap可以做到get和put都是O(1)。因?yàn)檫€有put函數(shù)，要可以remove least recently used cache，所以還需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄順序，自然想到list。set以及delete操作在LinkedList里面都是O(1)，就是要找到已存在的key這個(gè)操作在list是O(N)，因?yàn)榧匆獎(jiǎng)h除least recently的，也要加most recently的，所以是個(gè)double linked list?？梢园裮ap里面的value信息改成key在list里面該key對(duì)應(yīng)的list node，然后在list里面存value信息。這其實(shí)也就是LinkedHashMap可以做的。

public class LRUCache {
    class ListNode {
        ListNode prev;
        ListNode next;
        int val = 0;
        int key = 0;
        ListNode() {}
        ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    // new node(most recently) add to the tail part
    public void append(ListNode node) {
        node.prev = tail.prev;
        tail.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }
    
    // least recently node need to be remove from head
    public void remove() {
        remove(head.next);
    }

    // remove the certain node
    public void remove(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    ListNode head, tail;
    Map map;
    int remain;
    public LRUCache(int capacity) {
        remain = capacity;
        // map for get
        map = new HashMap();
        // list for put 
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if(map.containsKey(key)) {
            // remove the key node to the tail
            int value = map.get(key).val;
            put(key, value);
            return value;
        }
        else return -1;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)) {
            ListNode node = map.get(key);
            node.val = value;
            remove(node);
            append(node);
        }
        else {
            // not contain, check if count > capacity
            // remove the least recent node in list & map
            if(remain == 0) {
                map.remove(head.next.key);
                remove();
                remain++;
            }
            ListNode node = new ListNode(key, value);
            append(node);
            map.put(key, node);
            remain--;
        }
    }
}

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

題目鏈接：https://leetcode.com/problems...

上一題是只考慮出現(xiàn)的時(shí)間，這題加了frequency。那么再加一個(gè)map存freq應(yīng)該是可行的?，F(xiàn)在node除了要保存順序還得保存freq，感覺(jué)上像是個(gè)二維的，先按freq排序再考慮出現(xiàn)順序。每次得保存下這個(gè)freq出現(xiàn)最早的值，再出現(xiàn)的時(shí)候，要從這freq里刪了，移到下一個(gè)freq的tail上。想了下感覺(jué)還是不太好做，看了網(wǎng)上的答案。
參考這個(gè)博客：
http://bookshadow.com/weblog/...

first -> point to the freqNode with freq = 1
Map freqMap
relation between freqNode:
first(freq 0) <-> freq 1 <-> freq 2 <-> ......
Map keyMap

get(key):

case 1: return -1

case 2: exist =>

find keyNode and remove from freqNode, if cur freqNode has no element, remove freqNode

find freqNode through freqMap,

find next freqNode(freq + 1) through freqNode,

add keyNode to the tail of next freqNode

put(key, value)

case 1: not exist in keyMap => add to the tail of freqNode with freq = 1

case 2: exist =>

find keyNode, set value and remove from freqNode, if cur freqNode has no element, remove freqNode

find freqNode through freqMap,

find next freqNode(freq + 1) through freqNode,

add keyNode to the tail of next freqNode

其中，keyNode和keyMap和上一題一樣都是可以用LinkedHashMap來(lái)實(shí)現(xiàn)的。那么這里可以稍微改一下，把keyMap里面直接放然后用一個(gè)LinkedHashSet來(lái)存所有有相同freq的keyNode，只需要存key即可。

public class LFUCache {
    class freqNode {
        int freq = 0;
        freqNode prev, next;
        // store keys
        LinkedHashSet keyNodes = new LinkedHashSet();
        freqNode() {}
        freqNode(int freq) { this.freq = freq; }
        
        public int delete() {
            // if(keyNodes.isEmpty()) return;
            int key = keyNodes.iterator().next();
            keyNodes.remove(key);
            return key;
        }
        public void delete(int key) {
            // if(!keyNodes.contains(key)) return;
            keyNodes.remove(key);
        }
        public void append(int key) {
            keyNodes.add(key);
        }
    }
    
    int remain;
    // key, freqNode pair
    Map freqMap;
    // key, value pair
    Map keyMap;
    freqNode first;
    freqNode last;
    public LFUCache(int capacity) {
        this.remain = capacity;
        freqMap = new HashMap();
        keyMap = new HashMap();
        first = new freqNode();
        last = new freqNode();
        first.next = last;
        last.next = first;
    }
    
    public int get(int key) {
        if(!keyMap.containsKey(key)) return -1;
        else {
            updateFreq(key);
            return keyMap.get(key);
        }
    }
    
    public void put(int key, int value) {
        if(!keyMap.containsKey(key)) {
            if(remain == 0) {
                if(first.next.freq == 0) return;
                // remove the least frequent
                int del = first.next.delete();
                keyMap.remove(del);
                freqMap.remove(del);
                remain++;
            }
            // update map and add node
            keyMap.put(key, value);
            update(first, key);
            remain--;
        }
        else {
            updateFreq(key);
            keyMap.put(key, value);
        }
    }
    
    
    
    private void updateFreq(int key) {
        freqNode node = freqMap.get(key);
        update(node, key);
        
        // remove current node if has no keyNodes
        node.delete(key);
        if(node.keyNodes.size() == 0) {
            removeNode(node);
        }
    }
    
    private void update(freqNode node, int key) {
        // append to the next freq
        addAfterNode(node);
        node.next.append(key);
        // update freqMap key with next freqNode
        freqMap.put(key, node.next);
    }
    
    private void addAfterNode(freqNode node) {
        if(node.next.freq != node.freq + 1) {
            freqNode newNode = new freqNode(node.freq + 1);
            freqNode temp = node.next;
            node.next = newNode;
            newNode.prev = node;
            temp.prev = newNode;
            newNode.next = temp;
            node = null;
        }
    }
    
    private void removeNode(freqNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */