题解 | #设计LRU缓存结构#

本文仅用于本人记录

好家伙，第一次见这题，我整整弄了两小时。。。。。

一开始想着只用一个哈希表，题目的set和get都是o(1)的，可是还得处理当hashmap缓存大于k个键值对的时候清理掉最久远没set更新或者没get访问的键值对呀！所以我第一想到的就是对每个元素加一个power，代表建立该键值对的时间，越大说明越新，越小说明很久没更新/访问了。可是这样每次set和get就是o(n)了，严重超时。。。。
然后看题解，牛逼啊，用哈希表实现set和get的o(1)；然后用一个链表真实存储这些数据节点（哈希表本身不创造数据节点）。这样每次操作了set或者get就将对应节点（通过哈希表可以快速o(1)地找到那个节点）挪到链表头结点后第一位去，表示最新。删除也只是要移出哈希表的那个对应节点键值对就行了，真实的节点在链表其实删不删都无所谓。
当初我还不信邪，硬是要单向链表。。。结果发现还是双向链表简洁。

import java.util.*;

 class Listnode{
    int key;
    int value;
    Listnode next = null;
    Listnode prev = null;
 }
public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        HashMap<Integer,Listnode> hashMap = new HashMap<>();
        Listnode head = new Listnode();
        ArrayList<Integer> arrays = new ArrayList<>();
        for(int i = 0;i < operators.length;i++){
            if(hashMap.size() > k){
                Listnode iter = head;
                for(int j = 0;j < k;j++){
                    iter = iter.next;
                }
                hashMap.remove(iter.next.key);
                iter.next.prev = null;
                iter.next = null;
            }
            if(operators[i][0] == 1){
                if(hashMap.get(operators[i][1]) != null){
                    Listnode node = hashMap.get(operators[i][1]);
                    node.value = operators[i][2];
                    hashMap.put(operators[i][1],node);
                    moveToHead(head,node);
                }
                else{
                    Listnode node = new Listnode();
                    node.key = operators[i][1];
                    node.value = operators[i][2];
                    hashMap.put(operators[i][1],node);
                    moveToHead(head,node);
                }
            }
            else if(operators[i][0] == 2){
                if(hashMap.get(operators[i][1]) != null){
                    arrays.add(hashMap.get(operators[i][1]).value);
                    moveToHead(head,hashMap.get(operators[i][1]));
                }else{
                    arrays.add(-1);
                }
            }
        }
        int[] result = new int[arrays.size()];
        int i = 0;
        for (Integer array : arrays) {
            result[i++] = array;
        }
        return result;
   }
    void moveToHead(Listnode head,Listnode node){
        if(node.next != null && node.prev != null){
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }

        if(head.next != null){
            head.next.prev = node;
        }
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }
}