【无标题】

leecode-146LRU思路:
LruCache的原理,设置链表,根据访问时间排序,越近访问元素,越接近表头。若cache满,则淘汰末尾元素。

一:双链表方法

//定义链表数据结构:
class Node {				//使用双链表结构,便于进行位置的调换。
        private int key;
        private int value;
        Node pre;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
//构造器及成员变量
	final int capacity;   // cache 容量大小
    int size;				// 记录已存多少元素
    Node head;			//头结点
    public LRUCache(int capacity){
        head = new Node(0, 0);
         this.capacity = capacity;
         this.size = 0;
    }

//get 方法
public int get(int key)
    {
        Node t = head.next; 
        
        while (t!=null){  				//遍历双链表
            if (t.key==key){ 			//若key对应的元素已存在
                t.pre.next = t.next;
                if (t.next!=null) {		// 预防 t 为最后一个节点,造成空指针
                    t.next.pre = t.pre;
                }
                t.pre = head;
                t.next = head.next;
                if (head.next!=null) { 	//同上
                    head.next.pre = t;
                }
                head.next = t;
                return t.value;
            }else {			
                t = t.next;
            }
        }

        return -1;				// 若key对应元素不在cache 则返回-1
    }
// push
public void put(int key, int value) {
        Node t = head.next;
        while (t!=null){						// 遍历双链表
            if (t.key==key){					// 若 key对应元素已存在,则删除该元素
            										(或者更新value调到表头)
                t.pre.next = t.next;
                if (t.next.pre!=null) {		// 预防空指针
                    t.next.pre = t.pre;
                }
                t.pre = head;
                t.next = head.next;
                if (head.next.pre!=null) {
                    head.next.pre = t;
                }
                head.next = t;
                return;
            }else {
                t = t.next;
            }
        }

        Node newNode = new Node(key,value); 	//创建key-value 节点,插入表头
        if (size !=0 ){
            head.next.pre = newNode;
            newNode.next = head.next;
        }
        head.next = newNode;
        newNode.pre = head;
        
        if (this.size >= this.capacity){       // 若cache已满,淘汰最后一个元素
            Node te = head;
            while (te.next.next != null){
                te = te.next;
            }
            te.next = null;

        }else {
            this.size = this.size+1;
        }
    }

这种双链表的方法,也可实现,思路简单,但是代码相对比较繁琐。
每次寻找key对应的元素都需要遍历双链表,get和set方法时间复杂度都是O(n).
基于此,可以很容易的发现,若想提高效率,关键的便是寻找更优的查找key对应元素节点的方法。

==》 加入 HashMap。

//构造器
	public Node head;    // 设置双链表,设置表头、表尾节点,更加方便的进行节点位置的调整
    public Node tail;
    public HashMap<Integer, Node> map;
    public int size;
    private int capacity;

    public LRUCache(int capacity) {
        this.head = new Node(-1, 1);
        this.tail = new Node(-1, -1);
        this.capacity = capacity;
        this.head.next = tail;
        this.tail.pre = head;
        this.map = new HashMap<Integer, Node>();
        this.size = 0;
    }
// get 方法
 public int get(int key) {
        Node t = map.get(key);

        if (t == null) {   			// 若节点不存在 ,返回-1 
            return -1;
        }
        					
        t.pre.next = t.next;		// 若节点存在,则调整至表头并返回节点value值
        t.next.pre = t.pre;
        head.next.pre = t;
        t.next = head.next;
        head.next = t;
        t.pre = head;
        return t.value;

    }
//set方法
 public void put(int key, int value) {

        Node t = map.get(key);
        if (t != null) {						//若节点存在,更新value值,并调到表头
            t.value = value;

            t.pre.next = t.next;
            t.next.pre = t.pre;

            head.next.pre = t;
            t.next = head.next;
            head.next = t;
            t.pre = head;
            map.put(key,t);						// 更新 hashMap的元素	
        } else {
            t = new Node(key, value);			//节点不存在。则创建节点加到表头,并加入hashMaP
            head.next.pre = t;
            t.next = head.next;
            head.next = t;
            t.pre = head;
            map.put(key,t);
            size++;								// cache存放元素数量+1
            if (size > capacity) {				// 注意是否超出cache容量,若是则淘汰表尾元素
                map.remove(tail.pre.key);
                tail.pre = tail.pre.pre;
                tail.pre.next = tail;
            }
        }
    }

总结:
1.关于双链表的 表头表尾 使用。
2.对链表遍历注意空指针的存在。
3.hashMap在查询元素时的高性能表现

回顾:

HashMap HashTable LinkedHashMap TreeMap

上一篇:网络流


下一篇:python压缩包笔记12.14