程式員代碼面試指南刷題--第九章.設計LRU緩存結構

題目描述

設計LRU緩存結構，該結構在構造時确定大小，假設大小為K，并有如下兩個功能

set(key, value)：将記錄(key, value)插入該結構
get(key)：傳回key對應的value值
           

[要求]

set和get方法的時間複雜度為O(1)
某個key的set或get操作一旦發生，認為這個key的記錄成了最常使用的。
當緩存的大小超過K時，移除最不經常使用的記錄，即set或get最久遠的。
           

輸入描述:

第一行兩個個整數N, K，表示操作數量以及緩存結構大小

接下來N行，第一行一個整數opt表示操作類型。

若opt=1，接下來兩個整數x, y，表示set(x, y)

若opt=2，接下來一個整數x，表示get(x)，若x未出現過或已被移除，則傳回-1

輸出描述:

對于每個操作2，輸出一個答案

示例1

輸入

6 3
1 1 1
1 2 2
1 3 2
2 1
1 4 4
2 2

輸出

1
-1
           

解法一：雙端連結清單+兩個map

import java.io.*;
import java.util.*;
public class Main{
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        
        String[] ss = br.readLine().trim().split(" ");
        int nums = Integer.parseInt(ss[0]);
        int capcity = Integer.parseInt(ss[1]);
        fun(nums,capcity);
    }
    public static void fun(int nums,int capcity) throws IOException {
    	MyCache<Integer,Integer> mycache = new MyCache(capcity);
    	for(int i=0;i<nums;i++) {
    		String[] info = br.readLine().trim().split(" ");
    		if("1".equals(info[0])) {
    			int key = Integer.parseInt(info[1]);
    			int val = Integer.parseInt(info[2]);
    			mycache.set(key, val);
    		}else {
    			int key = Integer.parseInt(info[1]);
    			Integer res = mycache.get(key);
    			System.out.println(res==null?-1:res);
    		}
    	}
    }
}
class Node<V>{
    V val;
    Node<V> last;
    Node<V> next;
    public Node(V val){
        this.val = val;
    }
}
class DoubleLink<V>{
    Node<V> head;
    Node<V> tail;
    public DoubleLink(){
        head = null;
        tail = null;
    }
    public void addNode(Node<V> node){
        if(node==null) return;
        if(tail==null){
            head = node;
            tail = node;
        }else{
            tail.next = node;
            node.last = tail;
            tail = node;
        }
    }
    public void moveNodeToTail(Node<V> node){
        if(node==null) return;
        if(node==tail) return;
        if(node==head){
            head = head.next;
            head.last = null;
        }else {
            node.last.next = node.next;
            node.next.last = node.last;
        }
        tail.next = node;
        node.last = tail;
        tail = node;
        node.next = null;
    }
    public Node<V> removeHead(){
        if(head==null) return null;
        Node<V> res = head;
        if(tail==head){
            head = null;
            tail = null;
        }else{
            head = head.next;
            head.last = null;
            res.next = null;
        }
        return res;
    }
}
class MyCache<K,V>{
    HashMap<K,Node<V>> keyNode;
    HashMap<Node<V>,K> nodeKey;
    int capacity;
    DoubleLink<V> link;
    public MyCache(int cap){
        keyNode = new HashMap<>();
        nodeKey = new HashMap<>();
        this.capacity = cap;
        link = new DoubleLink();
    }
    public V get(K key){
        if(keyNode.containsKey(key)){
            Node<V> res = keyNode.get(key);
            link.moveNodeToTail(res);
            return res.val;
        }
        return null;
    }
    public void set(K key,V val){
        if(keyNode.containsKey(key)){
            Node<V> node = keyNode.get(key);
            node.val = val;
            link.moveNodeToTail(node);
        }else{
            Node<V> node = new Node<V>(val);
            keyNode.put(key,node);
            nodeKey.put(node,key);
            link.addNode(node);
            if(keyNode.size()==capacity+1){
                removeMostUnused();
            }
        }
    }
    public void removeMostUnused(){
        Node<V> head = link.removeHead();
        K key = nodeKey.get(head);
        nodeKey.remove(head);
        keyNode.remove(key);
    }
}