我已经实现了一种 LRU 缓存，该缓存在大多数情况下都可以通过，但在一个难以调试的大型测试用例中却失败了。
class LRUCache {
Map<Integer, Node> map;
Node head;
Node tail;
int capacity;
int currentSize;
public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
this.currentSize = 0;
this.head = null;
this.tail = null;
}
public int get(int key) {
if(map.containsKey(key)){
Node node = map.get(key);
removeNode(node);
moveNodeAtTop(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
Node node = new Node(key, value);
removeKey(key);
if(map.size() == this.capacity && tail!=null){
removeKey(tail.key);
}
moveNodeAtTop(node);
map.put(key, node);
}
private void removeKey(int key){
Node node = map.get(key);
removeNode(node);
map.remove(key);
}
public void removeNode(Node node){
if (node == null) return;
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
if (node == tail) {
this.tail = node.prev;
}
if (node == head) {
this.head = node.next;
}
}
public void moveNodeAtTop(Node node){
if(this.head == null){
this.head = node;
this.tail = node;
}else{
node.next = this.head;
this.head.prev = node;
head = node;
}
}
private class Node{
Node next;
Node prev;
int value;
int key;
Node(int key, int value){
this.key = key;
this.value = value;
}
}
}
然后我在leetcode上看到一些代码讨论，有些人将head和tail保留为dummy或-1。他们将 head.next 视为头部，将 tail.prev 视为尾部。所有测试用例都传递该代码。然后我看到了破解编码面试书，它和我的方法类似，但是在 GitHub 上，他们有另一种方法。
我知道通过虚拟头和尾，我们可以摆脱空值。我认为我们可以通过Optional 实现同样的目标。我只是想了解哪个测试用例在没有虚拟头和尾的情况下失败了。
工作解决方案
private Map<Integer, Node> map;
private Node head;
private Node tail;
private int capacity;
public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
head = new Node(-1, -1);
tail = new Node(-1, -1);
join(head, tail);
}
private void join(Node node1, Node node2){
node1.next = node2;
node2.prev = node1;
}
private void joinBetweenNode(Node node1, Node node2, Node node3){
node2.prev = node1;
node2.next = node3;
node1.next.prev = node2;
node1.next = node2;
}
public int get(int key) {
if(map.containsKey(key)){
Node node = map.get(key);
removeNode(node);
moveNodeAtTop(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
removeKey(key);
if(map.size() == this.capacity && tail!=null){
removeKey(getLast().key);
}
Node node = new Node(key, value);
moveNodeAtTop(node);
map.put(key, node);
}
private void removeKey(int key){
Node node = map.get(key);
removeNode(node);
map.remove(key);
}
public void removeNode(Node node){
if (node == null || node.prev == null || node.next == null) return;
node.prev.next = node.next;
node.next.prev = node.prev;
}
public void moveNodeAtTop(Node node){
if(node == null) return;
joinBetweenNode(head, node, head.next);
}
public Node getLast() {
if (head.next == tail) {
return null; // list has 0 Nodes
}
return tail.prev;
}
private class Node{
Node next;
Node prev;
int value;
int key;
Node(int key, int value){
this.key = key;
this.value = value;
}
}
我不确定为什么第一个解决方案在某些边缘情况下失败。 如果有人需要请告诉我
我发现 moveNodeAtTop 的错误，我错过了将新头的前一个设置为 null
node.prev = null;所有leetcode测试用例的工作解决方案：
class LRUCache {
Map<Integer, Node> map;
Node head;
Node tail;
int capacity;
int currentSize;
public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
this.currentSize = 0;
this.head = null;
this.tail = null;
}
public int get(int key) {
if(map.containsKey(key)){
Node node = map.get(key);
removeNode(node);
moveNodeAtTop(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
Node node = new Node(key, value);
removeKey(key);
if(map.size() == this.capacity && tail!=null){
removeKey(tail.key);
}
moveNodeAtTop(node);
map.put(key, node);
}
private void removeKey(int key){
Node node = map.get(key);
removeNode(node);
map.remove(key);
}
public void removeNode(Node node){
if (node == null) return;
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
if (node == tail) {
this.tail = node.prev;
}
if (node == head) {
this.head = node.next;
}
}
public void moveNodeAtTop(Node node){
if(this.head == null){
this.head = node;
this.tail = node;
}else{
node.next = this.head;
this.head.prev = node;
head = node;
node.prev = null;
}
}
private class Node{
Node next;
Node prev;
int value;
int key;
Node(int key, int value){
this.key = key;
this.value = value;
}
}
}
是的，当你将一个节点设置为链表的第一个元素时，你需要确保你设置了node.prev = null，与最后一个元素相同，你需要确保你设置了node.next = null
我也遇到了同样的错误，并通过为最后一个节点设置 node.next = null 来修复它。 你还需要设置node.prev = l，我最初也忘记了。
public Node addLast(Node node) {
final Node l = last;
//next node of last node should be null
node.next = null;
last = node;
if (l == null)
first = node;
else
{
l.next = node;
node.prev = l;
}
size++;
return node;
}