利用hashmap+双向链表实现LRU缓存,头部存放较新的节点,尾部存放不常使用的节点。
维护size字段,为链表长度,当长度超过k时,删除尾部节点
import java.util.*;
public class Solution {
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
//链表节点类 class DNode{ DNode pre; DNode next; int key; int val; public DNode(){} public DNode(int key,int val){ this.key = key; this.val = val; } } //存放值 HashMap<Integer,DNode> map = new HashMap<>(); DNode head = new DNode(); DNode tail = new DNode(); int size = 0; int capacity ; public int[] LRU (int[][] operators, int k) { //初始化 this.capacity = k; this.head.next = tail; this.tail.pre = head; List<Integer> list = new ArrayList<>(); // write code here for(int i = 0;i<operators.length;i++){ int opt = operators[i][0]; if(opt==1){ set(operators[i][1],operators[i][2]); }else{ list.add(get(operators[i][1])); } } int[] res = list.stream().mapToInt(Integer::valueOf).toArray(); return res; } public void set(int key,int value){ DNode node = map.get(key); if(node!=null){ node.val = value; moveToHead(node); }else{ node = new DNode(key,value); addHead(node); map.put(key,node); size++; if(size>capacity){ size--; map.remove(tail.pre.key); deleteNode(tail.pre); } } } public int get(int key){ DNode dnode = map.get(key); if(dnode!=null){ //移动到队首 moveToHead(dnode); return dnode.val; }else{ return -1; } } private void moveToHead(DNode node){ //删除旧节点 deleteNode(node); //头节点新增 addHead(node); } private void deleteNode(DNode node){ node.pre.next = node.next; node.next.pre = node.pre; } private void addHead(DNode node){ node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; }
}