网站双域名,建站系统哪个比较好,谷歌下载官网,邯郸建设公司网站例题#xff1a; 分析#xff1a; 题目要求函数get和put要达到O(1)的时间复杂度#xff0c;可以用 hashMap 来实现#xff0c;因为要满足逐出最久未使用的元素的一个效果#xff0c;还需要配合一个双向链表来共同实现。链表中的节点为一组key-value。 我们可以用双向链表来…例题 分析 题目要求函数get和put要达到O(1)的时间复杂度可以用 hashMap 来实现因为要满足逐出最久未使用的元素的一个效果还需要配合一个双向链表来共同实现。链表中的节点为一组key-value。 我们可以用双向链表来储存数据key-value,当调用put方法添加数据时可以将数据key-value添加到双向链表的队头队头的元素表示最新使用的元素越靠近队尾就是最久未用的元素。 当调用get方法时若存在此元素则从双向链表中把该组数据key-value提到队头来。 代码实现
package leetcode;import java.util.HashMap;public class LRUCacheLeetcode146 {static class LRUCache {static class Node{Node next;Node prev;int key;int value;public Node(){}public Node(int key, int value) {this.key key;this.value value;}}static class DoublyLinkedList{Node head;Node tail;public DoublyLinkedList() {head tail new Node();head.next tail;tail.prev head;}//头部添加 head-1-2-tail 假如添加3public void addFirst(Node newNode){Node oldFirst head.next;oldFirst.prev newNode;head.next newNode;newNode.prev head;newNode.next oldFirst;}//已知节点删除 head-1-2-tail 假如删除2public void remove(Node node){Node prev node.prev;Node next node.next;prev.next next;next.prev prev;}//尾部删除public Node removeLast(){Node last tail.prev;remove(last);return last;}}private final HashMapInteger, Node map new HashMap();private final DoublyLinkedList list new DoublyLinkedList();private final int capacity;public LRUCache(int capacity) {this.capacity capacity;}public int get(int key) {if(!map.containsKey(key)){return -1;}Node node map.get(key);//hash表中存在该数据改组数据应放到队头//先从中删除原始数据list.remove(node);//再将改组数据添加到队头list.addFirst(node);return node.value;}public void put(int key, int value) {if(map.containsKey(key)){ //更新Node node map.get(key);node.value value;list.remove(node);list.addFirst(node);}else{ //添加Node newNode new Node(key, value);map.put(key, newNode);list.addFirst(newNode);if(map.size() capacity){Node removed list.removeLast();//删除hash表中的数据map.remove(removed.key);}}}}public static void main(String[] args) {LRUCache cache new LRUCache(2);cache.put(1, 1);cache.put(2, 2);System.out.println(cache.get(1)); // 1cache.put(3, 3);System.out.println(cache.get(2)); // -1cache.put(4, 4);System.out.println(cache.get(1)); // -1System.out.println(cache.get(3)); // 3}
}
