定义
实现一个lru，意味着在一个容器里边，他有一个淘汰的size。达到这个size之后，再进行插入，则会把尾部的数据淘汰掉，这个就是容量淘汰。
146. LRU Cache
https://leetcode.com/problems/lru-cache/
实现方案
要实现这样一个数据结构，首先我们选择使用双端链表。
使用双端链表设计的必要性，在剔除尾巴节点的时候比较方便，理论上只要tail节点前移。
在访问当前节点的时候，可以拿到前后节点，然后放到header上，双端链表的优势是O(1)。
image.png
优化思路
为每一个节点建立索引，索引选择hashmap，只关注双端链表的操作，使得查询的时候不从头部遍历。
代码
public class LRUCache {
private int size;
private int capacity;
private Entry header;
private Entry tail;
public LRUCache(int capacity) {
if(capacity < 0){
throw new IllegalStateException("capacity must not smaller than zero");
}
size = 0;
this.capacity = capacity;
header = new Entry();
tail = header;
}
public void printList(){
System.out.println("顺序");
Entry e = header;
while (e != null){
System.out.print(e.getKey()+","+e.getValue()+" ");
e = e.next;
}
System.out.println();
}
public void printListRevert(){
System.out.println("逆序");
Entry e = tail;
while (e != null){
System.out.print(e.getKey()+","+e.getValue()+" ");
e = e.pre;
}
System.out.println();
}
public int get(int key) {
Entry runner = header.next;
while (runner != null && runner.getKey() != key){
runner = runner.next;
}
if(runner == null || runner.getKey() != key){
return -1;
}else{
Entry pre = runner.getPre();
Entry next = runner.getNext();
pre.next = next;
if(next != null){
next.pre = pre;
}
Entry first = header.getNext();
header.next = runner;
runner.pre = header;
runner.next = first;
if(first != null){
first.pre = runner;
}
return runner.getValue();
}
}
public void put(int key, int value) {
Entry runner = header.getNext();
while (runner != null && runner.getKey() != key){
runner = runner.getNext();
}
if(runner == null){
Entry newNode = new Entry();
newNode.setKey(key);
newNode.setValue(value);
Entry first = header.next;
header.next = newNode;
newNode.pre = header;
newNode.next = first;
if(first != null){
first.pre = newNode;
}else{
tail = newNode;
}
size ++;
}else{
runner.setValue(value);
Entry pre = runner.getPre();
Entry next = runner.getNext();
pre.next = next;
if(next != null){
next.pre = pre;
}
Entry first = header.next;
header.next = runner;
runner.pre = header;
runner.next = first;
if(first != null){
first.pre = runner;
}else {
tail = runner;
}
}
afterHandler();
}
public void afterHandler(){
if(size > capacity){
while (tail.getNext() != null){
tail = tail.next;
}
Entry e = tail.pre;
e.next = null;
tail.pre = null;
tail = e;
size --;
}
printList();
}
private static class Entry{
private int key;
private int value;
private Entry next;
private Entry pre;
public Entry getPre() {
return pre;
}
public void setPre(Entry pre) {
this.pre = pre;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Entry getNext() {
return next;
}
public void setNext(Entry next) {
this.next = next;
}
}
}
数组版本
class LRUCache {
private static class Entry{
int key;
int value;
}
private Entry[] data ;
int capacity;
int index;
public LRUCache(int capacity) {
if(capacity < 0){
throw new IllegalStateException("capacity 要大于0");
}
this.capacity = capacity;
data = new Entry[capacity];
index = 0;
}
public int get(int key) {
int index = findElementIndex(key);
if(index == -1){
return -1;
}else {
Entry e = data[index];
if(index != 0){
moveEntryWithDrop(0,index);
data[0] = e;
}
return e.value;
}
}
public void put(int key, int value) {
int index = findElementIndex(key);
if(index == -1){
Entry newNode = new Entry();
newNode.key = key;
newNode.value = value;
moveEntryWithDrop(0,data.length);
data[0] = newNode;
this.index ++;
}else{
Entry e = data[index];
e.value = value;
moveEntryWithDrop(0,index);
data[0] = e;
}
}
private void moveEntryWithDrop(int index,int len){
if(index < data.length){
Entry cur = data[index];
Entry next = null;
int i = index + 1;
int times = 0;
while (i < data.length && times < len){
next = data[i];
data[i] = cur;
cur = next;
i ++;
times ++;
}
}
}
private int findElementIndex(int key){
int index = 0;
for(; index < data.length; index ++){
if(data[index] != null && data[index].key == key){
break;
}
}
return index == data.length ? -1 : index;
}
}
查询O（1）版
class LRUCache {
int size;
int capacity;
Entry head;
Entry tail;
Map<Integer,Entry> index;
private static class Entry{
int key;
int value;
Entry next;
Entry pre;
}
public LRUCache(int capacity) {
if(capacity < 0){
throw new IllegalStateException();
}
this.capacity = capacity + 1;
size = 0;
head = new Entry();
tail = new Entry();
head.next = tail;
tail.pre = head;
index = new HashMap<>();
}
public int get(int key) {
Entry e = getEntry(key);
return e == null ? -1 : e.value;
}
private Entry getEntry(int key){
Entry e = index.get(key);
if(e != null){
Entry preNode = e.pre;
Entry nextNode = e.next;
preNode.next = nextNode;
nextNode.pre = preNode;
Entry first = head.next;
head.next = e;
e.next = first;
first.pre = e;
}
return e;
}
public void put(int key, int value) {
Entry e = getEntry(key);
if(e == null){
e = new Entry();
e.key = key;
e.value = value;
Entry first = head.next;
head.next = e;
e.pre = head;
e.next = first;
first.pre = e;
size ++;
index.put(key,e);
fixAfterInsert();
}else{
e.value = value;
}
}
private void fixAfterInsert(){
if(tail.pre == head){
return;
}
if(size > capacity){
Entry drop = tail.pre;
Entry preNode = drop.pre;
preNode.next = tail;
tail.pre = preNode;
drop.pre = null;
drop.next = null;
index.remove(drop.key);
size --;
}
}
}
网友评论