Untitled
unknown
plain_text
2 years ago
1.9 kB
51
Indexable
public class Solution { class Node{ int key; int val; Node next; Node prev; public Node(int k, int v){ this.key = k; this.val = v; this.next = null; this.prev = null; } } int size; int cap; Node head; Node tail; HashMap<Integer, Node> map; public Solution(int capacity) { size = 0; cap = capacity; head = new Node(-1, -1); tail = new Node(-2, -2); head.next = tail; tail.prev = head; map = new HashMap<>(); } public void addToTail(Node x){ x.next = tail; x.prev = tail.prev; tail.prev = x; x.prev.next = x; } public void remove(Node y){ y.prev.next = y.next; y.next.prev = y.prev; } public void removeFromHead(){ map.remove(head.next.key); remove(head.next); size--; } public int get(int key) { if(!map.containsKey(key)){ return -1; }else{ Node x = map.get(key); int ans = x.val; remove(x); addToTail(x); return ans; } } public void set(int key, int value) { if(map.containsKey(key) == true){ // hit Node x = map.get(key); remove(x); addToTail(x); x.val = value; }else{ //miss if(size < cap){ Node nn = new Node(key, value); map.put(key, nn); addToTail(nn); size++; }else if(size == cap){ removeFromHead(); Node nn = new Node(key, value); map.put(key, nn); addToTail(nn); size++; } } } }
Editor is loading...