代码拉取完成,页面将自动刷新
package code;
/*
* 146. LRU Cache
* 题意:首先理解LRU思想,最久未被访问过的,最先被替换
* 难度:Hard
* 分类:Design
* 思路:hashmap + 双向链表。hashmap实现了O(1)的get,双向链表实现O(1)的put
* Tips:能想到双向链表,就不难了
* lc380
*/
import java.util.HashMap;
public class lc146 {
class Node { //定义一个Node类
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public class LRUCache {
HashMap<Integer, Node> map;
int capicity, count; //最大容量,当前容量
Node head, tail; //头节点,尾节点
public LRUCache(int capacity) {
this.capicity = capacity;
map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.pre = head;
head.pre = null;
tail.next = null;
count = 0;
}
public void deleteNode(Node node) { //两个方法
node.pre.next = node.next;
node.next.pre = node.pre;
}
public void addToHead(Node node) {
node.next = head.next;
node.next.pre = node;
node.pre = head;
head.next = node;
}
public int get(int key) {
if (map.get(key) != null) {
Node node = map.get(key);
int result = node.value;
deleteNode(node);
addToHead(node);
return result;
}
return -1;
}
public void put(int key, int value) {
if (map.get(key) != null) {
Node node = map.get(key);
node.value = value;
deleteNode(node);
addToHead(node);
} else {
Node node = new Node(key, value);
map.put(key, node);
if (count < capicity) {
count++;
addToHead(node);
} else {
map.remove(tail.pre.key);
deleteNode(tail.pre);
addToHead(node);
}
}
}
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。