算法题： 设计LRU缓存结构

本文主要是介绍算法题： 设计LRU缓存结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能

• set(key, value)：将记录(key, value)插入该结构
• get(key)：返回key对应的value值

[要求]

1. set和get方法的时间复杂度为O(1)
2. 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
3. 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案

示例1

输入：

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

复制返回值：

[1,-1]

复制说明：

第一次操作后：最常使用的记录为("1", 1)
第二次操作后：最常使用的记录为("2", 2)，("1", 1)变为最不常用的
第三次操作后：最常使用的记录为("3", 2)，("1", 1)还是最不常用的
第四次操作后：最常用的记录为("1", 1)，("2", 2)变为最不常用的
第五次操作后：大小超过了3，所以移除此时最不常使用的记录("2", 2)，加入记录("4", 4)，并且为最常使用的记录，然后("3", 2)变为最不常使用的记录

备注：

1 \leq K \leq N \leq 10^51≤K≤N≤105
-2 \times 10^9 \leq x,y \leq 2 \times 10^9−2×109≤x,y≤2×109

import java.util.*;
 
 
public class Solution {
    public static class LRUCache {
        // 双向链表节点定义
         class Node {
            int key;
            int val;
            LRUCache.Node prev;
            LRUCache.Node next;
        }
 
        private int capacity;
        //保存链表的头节点和尾节点
        private LRUCache.Node first;
        private LRUCache.Node last;
 
        private Map<Integer, LRUCache.Node> map;
 
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>(capacity);
        }
 
        public int get(int key) {
            LRUCache.Node node = map.get(key);
            //为空返回-1
            if (node == null) {
                return -1;
            }
            moveToHead(node);
            return node.val;
        }
 
        private void moveToHead(LRUCache.Node node) {
            if (node == first) {
                return;
            } else if (node == last) {
                last.prev.next = null;
                last = last.prev;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
 
            node.prev = first.prev;
            node.next = first;
            first.prev = node;
            first = node;
        }
 
        public void put(int key, int value) {
            LRUCache.Node node = map.get(key);
 
            if (node == null) {
                node = new LRUCache.Node();
                node.key = key;
                node.val = value;
 
                if(map.size() == capacity) {
                    removeLast();
                }
 
                addToHead(node);
                map.put(key, node);
            } else {
                node.val = value;
                moveToHead(node);
            }
        }
 
        private void addToHead(LRUCache.Node node) {
            if (map.isEmpty()) {
                first = node;
                last = node;
            } else {
                node.next = first;
                first.prev = node;
                first = node;
            }
        }
 
        private void removeLast() {
            map.remove(last.key);
            LRUCache.Node prevNode = last.prev;
            if (prevNode != null) {
                prevNode.next = null;
                last = prevNode;
            }
        }
 
        @Override
        public String toString() {
            return map.keySet().toString();
        }
    }
 
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
     
    public int[] LRU (int[][] operators, int k) {
        LRUCache lruLinkedHashMap = new LRUCache(3);
        List<Integer> result = new ArrayList<>();
        // write code here
        for (int i = 0; i < operators.length; i++) {
            int opt = operators[i][0];
            if(opt==1){
                lruLinkedHashMap.put(operators[i][1],operators[i][2]);
            }else if(opt==2){
                Object o = lruLinkedHashMap.get(operators[i][1]);
                if (o==null){
                    result.add(-1);
//                    return new int[]{operators[i][1], -1};
//                    System.out.println(Arrays.asList(operators[i][1],-1));
                }else{
                    result.add((Integer) o);
//                    return new int[]{operators[i][1],o};
//                    System.out.println(Arrays.asList(operators[i][1],o));
                }
            }
        }
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i]= result.get(i);
        }
        return res;
    }
}

这篇关于算法题： 设计LRU缓存结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！