|
解题思路
最先想到的是哈希表加单链表的方式：由于get和put都视为是一次使用，所以在get和put之后都要将节点移动到链表的最前面（最前面的表示最近一次使用的，显然最后面的一个就是要被淘汰的一个）
哈希表中记录的是key-value值，链表上只存放key值即可，不断地调整链表上的key的排列顺序即可实现最近最久未使用的排序效果。
这种做法问题挺多的，一个是map中没有存放key对应的链表节点，导致在寻找链表上的节点时需要顺序遍历链表，这导致我写的程序 花费300多ms...
改进的办法就是map中存放对应的链表节点，这样在调整顺序的时候可以直接从map中找到对应的节点，大大缩短时间。
另外，在删除的时候，我们需要删除链表最后一个节点，那么由这个需求，很容易想到循环单链表或者有头尾节点的双链表，这两种做法应该都是可以的，只不过 双链表可能操作起来更清晰 更舒服一些
最后，有一个完美的数据结构就可以解决这个问题，LinkedMapHashMap 它的特点是会按顺序将我们插入的节点链接起来，底层是用单链表实现的。
这样就方便了，get的时候 如果之前有这个key，那么就删除之前的数据，然后重新put到链表的末尾，显然链表的第一个元素就是我们需要删除的（如果需要的话），
put的时候先put，然后检查容量是否符合要求，决定是否删除第一个map元素。
代码
解法一：LinkedHashMap
?class LRUCache
{
? ? LinkedHashMap<Integer,Integer> map = null;
? ? int capacity;
? ? public LRUCache(int capacity) {
? ? ? map = new LinkedHashMap<>();
? ? ? ? this.capacity = capacity;
? ? }
? ? public int get(int key)
? ? {
? ? ? ? if(map.containsKey(key)){
? ? ? ? ? ? Integer value = map.get(key);
? ? ? ? ? ? map.remove(key);
? ? ? ? ? ? map.put(key,value);
? ? ? ? ? ? return ?value;
? ? ? ? }else{
? ? ? ? ? ? return -1;
? ? ? ? }
? ? }
? ? public void put(int key, int value) {
? ? ? ? if(map.containsKey(key)){
? ? ? ? ? ? map.remove(key);
? ? ? ? ? ? map.put(key,value);
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? map.put(key,value);
? ? ? ? ? if(map.size() > capacity){
? ? ? ? ? ? ? map.remove(map.keySet().iterator().next());
? ? ? ? ? }
? ? }
}
解法二：哈希表加单链表
class Node{
? ? Node next;
? ? int val;
? ? public Node() {
? ? }
? ? @Override
? ? public String toString() {
? ? ? ? return "Node{" +
? ? ? ? ? ? ? ? "next=" + next +
? ? ? ? ? ? ? ? ", val=" + val +
? ? ? ? ? ? ? ? '}';
? ? }
? ? public Node getNext() {
? ? ? ? return next;
? ? }
? ? public void setNext(Node next) {
? ? ? ? this.next = next;
? ? }
? ? public int getVal() {
? ? ? ? return val;
? ? }
? ? public void setVal(int val) {
? ? ? ? this.val = val;
? ? }
? ? public Node( int val) {
? ? ? ? this.val = val;
? ? }
}
class LRUCache {
? ? HashMap<Integer,Integer> map = null;
? ? int capactity;
? ? Node head = null;
? ? public LRUCache(int capacity) {
? ? ? ? head = ?new Node();
? ? ? ? head.next = null;
? ? ? ? this.capactity ?= capacity;
? ? ? ? map = new HashMap<>();
? ? }
? ? public int get(int key) {
? ? ? ? int res = ?map.getOrDefault(key,-1) ;
? ? ? ? if (res == -1){
? ? ? ? ? ? return -1;
? ? ? ? }else{
? ? ? ? ? ? //执行排序操作 移动到最前面
? ? ? ? ? ? Node p = head;
? ? ? ? ? ? Node q = p;
? ? ? ? ? ? p = p.next;
? ? ? ? ? ? while(p!=null){
? ? ? ? ? ? ? ? if(p.val == key){
? ? ? ? ? ? ? ? ? ? q.next = p.next;
? ? ? ? ? ? ? ? ? ? p.next = head.next;
? ? ? ? ? ? ? ? ? ? head.next = p;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ?q = p;
? ? ? ? ? ? ? ? ? ?p = p.next;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return res;
? ? ? ? }
? ? }
? ? public void put(int key, int value) {//put 也会使保持为最新的排序
? ? ? ? if(map.get(key) == null){
? ? ? ? ? ? if(map.size()<capactity){
? ? ? ? ? ? ? ? map.put(key,value);
? ? ? ? ? ? ? ? Node p,q=head;
? ? ? ? ? ? ? ? p = head.next;
? ? ? ? ? ? ? ? while(p!=null){
? ? ? ? ? ? ? ? ? ? q = p;
? ? ? ? ? ? ? ? ? ? p = p.next;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? q.next = new Node(key);
? ? ? ? ? ? ? ? get(key);
? ? ? ? }else{
? ? ? ? ? ? //执行删除
? ? ? ? ? ? ? ? map.put(key,value);
? ? ? ? ? ? ? ? Node p = head;
? ? ? ? ? ? ? ? Node q = p;
? ? ? ? ? ? ? ? p = head.next;
? ? ? ? ? ? ? ? while(p.next!=null){
? ? ? ? ? ? ? ? ? ? q = p;
? ? ? ? ? ? ? ? ? ? p = p.next;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? map.remove(p.val);
? ? ? ? ? ? ? ? p = null;
? ? ? ? ? ? ? ? q.next = null;
? ? ? ? ? ? ? ? //插入新的
? ? ? ? ? ? ? ? Node p1,q1=head;
? ? ? ? ? ? ? ? p1 = head.next;
? ? ? ? ? ? ? ? while(p1!=null){
? ? ? ? ? ? ? ? ? ? q1 = p1;
? ? ? ? ? ? ? ? ? ? p1 = p1.next;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? q1.next = new Node(key);
? ? ? ? ? ? ? ? get(key);
? ? ? ? ? ? }
? ? ? ? }else{
? ? ? ? ? ? //重复的key为修改
? ? ? ? ? ? map.put(key,value);
? ? ? ? ? ? get(key);
? ? ? ? }
? ? }
}
解法三：哈希表加双链表
?class LRUCache4
{
? ? LinkedHashMap<Integer,Integer> map = null;
? ? int capacity;
? ? public LRUCache4(int capacity) {
? ? ? map = new LinkedHashMap<>();
? ? ? ? this.capacity = capacity;
? ? }
? ? public int get(int key)
? ? {
? ? ? ? if(map.containsValue(key)){
? ? ? ? ? ? Integer value = map.get(key);
? ? ? ? ? ? map.remove(key);
? ? ? ? ? ? map.put(key,value);
? ? ? ? ? ? return ?value;
? ? ? ? }else{
? ? ? ? ? ? return -1;
? ? ? ? }
? ? }
? ? public void put(int key, int value) {
? ? ? ? if(map.containsKey(key)){
? ? ? ? ? ? map.remove(key);
? ? ? ? ? ? map.put(key,value);
? ? ? ? ? ? return;
? ? ? ? }
作者：lingluan533
链接：https://leetcode-cn.com/problems/lru-cache-lcci/solution/linkedhashmap-ha-xi-biao-yu-dan-lian-bia-a9kb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|