LRUCache 實作： 雙端佇列 + HashMap快速實作。

自己實作佇列（啞頭結點+ 啞尾結點實作 + 雙向佇列實作）（快速存盤） + HashMap快速查找（索引）：
主要思路
get:
當快取中不存在，則回傳-1；
當快取中存在，則佇列中移除，添加到雙端佇列末尾，回傳node.value;
put：思路：
判斷是否存在： 復用get方法：不存在回傳-1， 存在回傳當前value,并且將節點移動到末尾；
如果不存在，判斷是否記憶體已滿？
滿了，則洗掉隊頭結點，以及map中移除索引；
創建新節點，然后添加在佇列末尾，然后添加索引項，

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二維陣列 the ops
     * @param k int整型 the k
     * @return int整型一維陣列
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        List<Integer> list = new ArrayList<> ();
        LRUCache cache = new LRUCache(k);
        for(int[] arr : operators){
            if(arr[0] == 1){
                cache.put(arr[1] ,arr[2]);
            } else if(arr[0] == 2){
                //System.out.println(cache.get(arr[1]));
                list.add(cache.get(arr[1]));
            }
        }
        //List<String> ans = new ArrayList<>();
        //ans.toArray(new String[ans.size()]);
        int[] ans = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
           ans[i] = list.get(i);
        }
        return ans;
        //return ans.toArray(new int[ans.size()]);
    }
}
class ListNode {
    ListNode prev;
    ListNode next;
    int key;
    int value;
   
    public ListNode(int key_, int value_){
        key = key_;
        value = https://www.cnblogs.com/sidewinder/archive/2020/09/22/value_;
    }
}
class LRUCache{
    ListNode dummyHead = new ListNode(0,0);
    ListNode dummyTail = new ListNode(0,0);
    Map mp = new HashMap<> ();
    int capacity ;
    public LRUCache(int cap){    
        // 構建雙向佇列
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        capacity = cap;
    }
    
    // 查詢
    public int get(int key){
        // 不在快取中
        if(!mp.containsKey(key)){
            return -1;
        }
        ListNode node = mp.get(key);
        // 佇列中洗掉+ 加入佇列末尾；
        node.prev.next = node.next;
        node.next.prev = node.prev;
        
        node.next = dummyTail;
        node.prev = dummyTail.prev;
        dummyTail.prev.next = node;
        dummyTail.prev = node;
        return node.value;
    }
    
    //寫入
    public void put(int key, int value){
        //快取里面是否存在
        //存在 
        if(get(key) > -1){
             mp.get(key).value = value;
        }
        //不存在
        // 記憶體是否已滿
        else {
            if(mp.size() == capacity ){
                //洗掉隊首節點
                ListNode node = dummyHead.next;
                //鏈表中洗掉頭接待你
                node.prev.next = node.next;
                node.next.prev = node.prev;
                // map中洗掉
                mp.remove(node.key);
            }
            
             ListNode newNode = new ListNode(key, value);
            // 添加到末尾
            newNode.next = dummyTail;
            newNode.prev = dummyTail.prev;
            dummyTail.prev.next =  newNode;
            dummyTail.prev =  newNode;
            // 更新mp;
            mp.put(key, newNode);
        }
       
    }
}

標籤：其他

上一篇：Python爬蟲的常見依賴庫大全

下一篇：求大神指教，vector<string>陣列在進行元素查找時出現了一點問題