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 = value_;
    }
}
class LRUCache{
    ListNode dummyHead = new ListNode(0,0);
    ListNode dummyTail = new ListNode(0,0);
    Map<Integer, ListNode> 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);
        }
       
    }
}

LRUCache 实现: 双端队列 + HashMap快速实现。

上一篇:Shell的一些概念


下一篇:linux 防火墙selinux ,firewalld, iptables