iframe-proxy | Sunbelt Computer Software

86 lines (78 loc) · 2.33 KB

package code;
 * 146. LRU Cache
 * 题意：首先理解LRU思想，最久未被访问过的，最先被替换
 * 分类：Design
 * 思路：hashmap + 双向链表。hashmap实现了O(1)的get，双向链表实现O(1)的put
 * Tips：能想到双向链表，就不难了
 *      lc380
import java.util.HashMap;
public class lc146 {
    class Node {    //定义一个Node类
        int key;
        int value;
        Node pre;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
    public class LRUCache {
        HashMap<Integer, Node> map;
        int capicity, count;    //最大容量，当前容量
        Node head, tail;    //头节点，尾节点
        public LRUCache(int capacity) {
            this.capicity = capacity;
            map = new HashMap<>();
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.pre = head;
            head.pre = null;
            tail.next = null;
            count = 0;
        public void deleteNode(Node node) { //两个方法
            node.pre.next = node.next;
            node.next.pre = node.pre;
        public void addToHead(Node node) {
            node.next = head.next;
            node.next.pre = node;
            node.pre = head;
            head.next = node;
        public int get(int key) {
            if (map.get(key) != null) {
                Node node = map.get(key);
                int result = node.value;
                deleteNode(node);
                addToHead(node);
                return result;
            return -1;
        public void put(int key, int value) {
            if (map.get(key) != null) {
                Node node = map.get(key);
                node.value = value;
                deleteNode(node);
                addToHead(node);
            } else {
                Node node = new Node(key, value);
                map.put(key, node);
                if (count < capicity) {
                    count++;
                    addToHead(node);
                } else {
                    map.remove(tail.pre.key);
                    deleteNode(tail.pre);
                    addToHead(node);

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

lc146.java

Latest commit

History

lc146.java

File metadata and controls