设计LRU缓存结构

解题思路

1. 使用 HashMap：将 key 映射到对应的节点，这样可以在 O(1)O(1)O(1) 时间内查找元素。
2. 使用双向链表：保存缓存的顺序，最久未使用的元素在链表的尾部，最近使用的在头部。
   • 每次访问 get 或 set，将对应节点移动到链表头部。
   • 当缓存超出容量 capacity 时，移除链表尾部节点（最久未使用）。

实现细节

• 构造函数 Solution(int capacity)：初始化 capacity，以及 HashMap 和双向链表的头尾哨兵节点（dummy nodes），方便处理边界条件。
• 方法 get(int key)：如果 key 存在，则将该节点移动到链表头部并返回其 value；否则返回 -1。
• 方法 set(int key, int value)：如果 key 已存在，则更新其 value 并移动到链表头部；否则，插入新节点到头部。若超过容量，则移除链表尾部节点。

代码实现

import java.util.HashMap;

public class Solution {

    // 定义双向链表节点
    private class Node {
        int key, value; // 键值对
        Node prev, next; // 前后指针指向前后节点

        Node(int k, int v) { // 构造方法
            this.key = k;
            this.value = v;
        }
    }

    private int capacity; // LRU 缓存的最大容量
    private HashMap<Integer, Node> map; // 存储键值对<key, Node> 的映射，用于O(1)访问
    private Node head, tail; // 双向链表的哨兵头节点和尾节点

    public Solution(int capacity) {
        this.capacity = capacity; // 初始化缓存的容量
        this.map = new HashMap<>(); // 初始化哈希表
        // 初始化双向链表的哨兵节点（不存储实际数据，方便边界操作）
        this.head = new Node(0, 0); // 头哨兵节点
        this.tail = new Node(0, 0); // 尾哨兵节点
        head.next = tail; // 初始化链表，将头尾哨兵节点相连
        tail.prev = head;
    }

    // 获取缓存中指定键的值
    public int get(int key) {
        if (map.containsKey(key)) { // 检查键是否存在
            Node node = map.get(key); // 获取对应节点
            moveToHead(node); // 将该节点移到链表头部，标记为最近使用
            return node.value; // 返回对应的值
        }
        return -1; // 不存在则返回 -1
    }

    // 插入或更新缓存中的键值对
    public void set(int key, int value) {
        if (map.containsKey(key)) { // 如果键已存在
            Node node = map.get(key); // 获取已有节点
            node.value = value; // 更新节点的值
            moveToHead(node); // 将节点移到链表头部，标记为最近使用
        } else {
            // 若键不存在，则创建新节点
            Node newNode = new Node(key, value);
            map.put(key, newNode); // 将新节点加入哈希表
            addNode(newNode); // 插入新节点到链表头部
            // 如果超过容量，移除最久未使用节点（链表尾部节点）
            if (map.size() > capacity) {
                Node tail = removeTail(); // 删除尾部节点
                map.remove(tail.key); // 从哈希表中移除对应的键
            }
        }
    }

    // 辅助方法：在链表头部添加节点
    private void addNode(Node node) {
        node.next = head.next; // 将新节点的 next 指向 head 的 next
        node.prev = head; // 新节点的 prev 指向 head
        head.next.prev = node; // 将 head 原来的 next 的 prev 指向新节点
        head.next = node; // head 的 next 指向新节点
    }

    // 辅助方法：从链表中移除节点
    private void removeNode(Node node) {
        node.prev.next = node.next; // 将 node 的前节点的 next 指向 node 的 next
        node.next.prev = node.prev; // 将 node 的后节点的 prev 指向 node 的 prev
    }

    // 辅助方法：将节点移动到链表头部（表示最近使用）
    private void moveToHead(Node node) {
        removeNode(node); // 先从链表中删除节点
        addNode(node); // 然后再添加到链表头部
    }

    // 辅助方法：移除链表尾部节点并返回该节点（最久未使用节点）
    private Node removeTail() {
        Node res = tail.prev; // 获取尾节点前的节点
        removeNode(res); // 从链表中删除
        return res; // 返回被移除的节点
    }
}

代码详解

1. Node 类：

   • Node 是双向链表的节点类，包含 key 和 value，以及 prev 和 next 指针用于双向链接。

2. 构造方法 Solution(int capacity)：

   • 初始化 capacity 和 map，并创建链表的 head 和 tail 哨兵节点。
   • 通过将 head.next 指向 tail，tail.prev 指向 head，形成一个空的双向链表（仅有哨兵节点）。

3. 方法 get(int key)：

   • 检查 key 是否在 map 中。
   • 如果在，则通过 moveToHead(node) 将对应节点移到链表头部，以标记该节点为最近使用。
   • 返回节点的 value。
   • 如果 key 不在 map 中，则返回 -1。

4. 方法 set(int key, int value)：

   • 检查 key 是否在 map 中。
     • 如果 key 已存在，更新其 value，并调用 moveToHead(node) 将节点移到链表头部。
     • 如果 key 不存在，创建新节点，并插入到链表头部。
     • 检查 map 的大小是否超过 capacity，若超过则调用 removeTail() 删除链表尾部节点，并从 map 中移除对应键。

5. 辅助方法：

   • addNode(Node node)：将新节点插入到链表头部，链表更新顺序为 head <-> node <-> head.next。
   • removeNode(Node node)：从链表中删除指定节点。
   • moveToHead(Node node)：将节点先删除，再插入链表头部，更新为最近使用。
   • removeTail()：删除链表尾部节点（最久未使用节点），并返回该节点。

关键点总结

• HashMap 作为缓存记录的快速查找结构，使得 get 和 set 操作在 时间完成。
• 双向链表 维护 LRU 顺序，头部表示最近使用，尾部表示最久未使用。
• 容量管理：当超出容量时，通过 removeTail() 删除尾节点（最久未使用），并从 map 中移除。

LinkedHashMap<Integer ,Integer> map;
int capacity;

public Solution(int capacity) {
    // write code here
    this.capacity=capacity;
    map=new LinkedHashMap<>(capacity);
}

public int get(int key) {
    // write code here
    if(map.containsKey(key)){
        int val=map.get(key);
        map.remove(key);
        map.put(key ,val);
        return val;
    }
    return -1;
}

public void set(int key, int value) {
    // write code here
    if(map.containsKey(key)){
        map.remove(key);
    }else if(map.size()==capacity){
        map.remove(map.keySet().iterator().next());
    }
    map.put(key ,value);
}

调库

public class Solution {
    LinkedHashMap<Integer, Integer> lru;

    public Solution(int capacity) {
    // write code here
        lru = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return this.size() > capacity;
            }
        };
    }

    public int get(int key) {
    // write code here
        return lru.getOrDefault(key, -1);
    }

    public void set(int key, int value) {
    // write code here
        lru.put(key, value);
    }
}

import java.util.*;

public class Solution {
    private int capacity;
    private List<Integer> status;//使用频率
    private Map<Integer, Integer> map; //存数据

    public Solution(int capacity) {
        this.capacity = capacity;
        this.status = new ArrayList<Integer>();
        this.map = new HashMap<Integer, Integer>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            status.removeIf(o->o.equals(key));
            status.add(key);
            return map.get(key);
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) {
            status.removeIf(o->o.equals(key));
            status.add(key);
            map.put(key, value);
            return;
        } else {
            if (map.size() >= capacity) {
                map.remove(status.get(0));
                status.remove(0);
                status.removeIf(o->o.equals(key));
                status.add(key);
                map.put(key, value);
            } else {
                status.removeIf(o->o.equals(key));
                status.add(key);
                map.put(key, value);
            }
        }
    }
}

// 不想用链表，用队列可以嘛？
public class Solution {
    private Deque<Integer> queue;
    private Map<Integer, Integer> map;
    private int capacity;
    public Solution(int capacity) {
        // write code here
        queue = new ArrayDeque<>();
        map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        // write code here
        // 更新缓存
        if (map.containsKey(key)) {
            queue.remove(Integer.valueOf(key));
            queue.addFirst(key); // 访问过的一律放到队头
            return map.get(key);
        }

        return -1;
    }


    public void set(int key, int value) {
        // write code here
        if (map.containsKey(key)) { // 存在就放到队头
            queue.remove(Integer.valueOf(key));
            queue.addFirst(key);
        } else { // 不存在就加入队头
            if (queue.size() == capacity) { // 容量满了，删一个
                int last = queue.getLast();
                // System.out.println(last+"-->"+map.get(key)+12);
                map.remove(last);
                queue.removeLast(); // 删掉最不常用的（队尾）
            }
            queue.addFirst(key);
        }
        map.put(key, value);
    }
}

import java.util.*;


public class Solution {
    // 缓存容量
    private int capacity;
    // 缓存链当前头节点
    private Node curHead;
    // 缓存链当前尾节点
    private Node curTail;
    // 缓存链当前长度
    private int curLen;
    // 存放缓存链的元素，便于查找，key是插入的数据的key，value是插入的数据所构成的节点Node
    private HashMap<Integer, Node> map;
    // 双向链表，记录当前缓存顺序
    class Node {
        // 需要存储的数据的key
        int key;
        // 需要存储的数据的value
        int val;
        Node pre;
        Node next;
        Node(int key, int value, Node pre, Node next) {
            this.key = key;
            this.val = value;
            this.pre = pre;
            this.next = next;
        }
    }

    public Solution(int capacity) {
// write code here
        this.capacity = capacity;
        this.curHead = null;
        this.curTail = null;
        this.curLen = 0;
        map = new HashMap<Integer, Node>();
    }

    public int get(int key) {
// write code here
        // 不存在返回-1
        if (!map.containsKey(key)) return -1;
        // 存在且该节点不是头结点，则将key对应的数据标记为最近使用，并返回数据值，
        // 通过map得到Node，再由Node得到数据值
        else {
            Node node = map.get(key);
            if (curHead != node) markRecently(node);
            return map.get(key).val;
        }
    }

    public void set(int key, int value) {
// write code here
        // 存在该节点
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 不是头结点，则更改当前节点值，将key对应的数据标记为最近使用
            if (node != curHead) {
                node.val = value;
                markRecently(node);
                // 是头结点，则更改当前节点值
            } else node.val = value;
            // 不存在该节点
        } else {
            // 如果头节点为空，则设置头结点和尾节点
            if (curHead == null) {
                // 设置头节点
                curHead = new Node(key, value, null, null);
                // 设置尾节点
                curTail = curHead;
                // 如果头节点不为空
            } else {
                // 创建该节点，并指向当前头结点
                Node node = new Node(key, value, null, curHead);
                // 将当前头节点指向该节点
                curHead.pre = node;
                // 将该节点置为当前头结点
                curHead = node;
            }
            // 当前链表长度+1
            curLen++;
            // 将当前节点加入map中
            map.put(key, curHead);
            // 如果当前链表超长，则进行末尾节点删除
            if (curLen > capacity) {
                // 删除map中的末尾节点
                map.remove(curTail.key);
                // 将链表中末尾节点的前序节点置为当前末尾节点
                curTail = curTail.pre;
                // 对末尾节点（此时的末尾节点为原末尾节点的前序节点）的后续节点置空
                curTail.next = null;
                // 当前长度-1
                curLen--;
            }
        }
    }
    // 将节点置为最近使用,即移到链表头部，已排除头部节点
    public void markRecently(Node node) {
        // 如果是末尾节点
        if (node == curTail) {
            // 将链表中末尾节点的前序节点置为当前末尾节点
            curTail = curTail.pre;
            // 对末尾节点（此时的末尾节点为原末尾节点的前序节点）的后序节点置空
            curTail.next = null;
        // 如果是中建节点
        } else {
            // 将该节点的后序节点置为该节点的前序节点的后序节点
            node.pre.next = node.next;
            // 将该节点的前序节点置为该节点的后序的前序节点
            node.next.pre = node.pre;
        }
        // 将该节点置为头结点的前序节点
        curHead.pre = node;
        // 将当前头节点置为该节点的后序节点
        node.next = curHead;
        // 当该节点置为当前头节点
        curHead = node;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

import java.util.*;

public class Solution {
    int capacity;
    // key -> Node
    Map<Integer, Node> cache;
    // lru 
    DeLinkedList lru;
    public Solution(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.lru = new DeLinkedList();
    }

    public int get(int key) {
        if ( cache.containsKey(key) ) {
            Node node = cache.get(key);
            lru.remove(node);
            lru.addLast(node);
            return node.val;
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if ( cache.containsKey(key) ) {
            Node node = cache.get(key);
            node.val = value;
            lru.remove(node);
            lru.addLast(node);
        } else {
            Node node = new Node(key, value);
            cache.put(key, node);
            lru.addLast(node);
            // evict
            if ( cache.size() > this.capacity ) {
                Node evict = lru.removeFirst();
                cache.remove(evict.key);
            }
        }
    }
}

class Node {
    int key;
    int val;
    Node pre;
    Node next;
    public Node(){}
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class DeLinkedList {
    // 虚拟节点
    Node head;
    Node tail;

    public DeLinkedList() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public void addLast(Node node) {
        Node last = tail.pre;
        last.next = node;
        node.pre = last;
        node.next = tail;
        tail.pre = node;
    }

    public Node removeFirst() {
        Node remove = head.next;
        head.next = remove.next;
        remove.next.pre = head;
        return remove;
    }

    public Node remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node;
    }

}

class Solution {
        int capacity = 0;
        List<Integer> list = new ArrayList<>();
        Map<Integer,Integer> mp = new HashMap<>();
        public Solution(int capacity) {
            // write code here
            this.capacity = capacity;
        }
        public int get(int key) {
            // write code here
            if(!mp.containsKey(key)){
                return -1;
            }
            list.remove(Integer.valueOf(key));
            list.add(0,key);
            return mp.get(key);
        }

        public void set(int key, int value) {
            // write code here
            if(mp.containsKey(key)){
                list.remove(Integer.valueOf(key));
                list.add(0,key);
                mp.remove(key);
                mp.put(key,value);
                return;
            }
            if(list.size() < capacity){
                list.add(0,key);
                mp.put(key,value);
            } else{
                mp.remove(list.get(capacity-1));
                list.remove(capacity - 1);
                list.add(0,key);
                mp.put(key,value);
            }
        }
    }

public static class BinaryNode {
        int x;
        int y;

        BinaryNode(int x, int y) {
            this.x = x;
            this.y = y;
        }

        BinaryNode next = null;
    }

    // 设计lru
    public static ArrayList<String> LRUCache(ArrayList<String> operators, ArrayList<ArrayList<Integer>> param, int capacity) {
        // write code here
        Map<Integer, BinaryNode> keyHashMap = new HashMap<Integer, BinaryNode>();
        ArrayList<String> resultList = new ArrayList<String>();
        BinaryNode firNode = new BinaryNode(-1, -1);
        for (int i = 0; i < operators.size(); i++) {
            if ("set".equals(operators.get(i))) {
                resultList.add(set(param.get(i),keyHashMap,firNode,capacity));
            } else if ("get".equals(operators.get(i))) {
                resultList.add(get(param.get(i),keyHashMap,firNode));
            }
        }
        return resultList;
    }

    public static String set(ArrayList<Integer> params, Map<Integer, BinaryNode> keyHashMap,BinaryNode firNode,int capacity) {
        Integer key = params.get(0);
        Integer value = params.get(1);
        BinaryNode node = new BinaryNode(key, value);
        // 存在 清除 队尾补齐
        if (keyHashMap.containsKey(key)) {
            removeTempNode(firNode,node);
            setBinaryNodeToLast(firNode,node);
        } else {
            // 不存在
            // 超过空间大小 清除头 队尾补齐
            if (keyHashMap.keySet().size() >= capacity) {
                keyHashMap.remove(firNode.next.x);
                removeFirNode(firNode);
                setBinaryNodeToLast(firNode,node);
            } else {
                // 未超过空间大小 队尾补齐
                setBinaryNodeToLast(firNode,node);
            }
        }
        keyHashMap.put(key,new BinaryNode(key, value));
        return "null";
    }

    public static String get(ArrayList<Integer> params, Map<Integer, BinaryNode> keyHashMap,BinaryNode firNode) {
        Integer key = params.get(0);
        // get也会默认为最常使用
        if (!keyHashMap.containsKey(key)) {
            return "-1";
        } else {
            BinaryNode node = keyHashMap.get(key);
            // 清除 放队尾
            removeTempNode(firNode,node);
            setBinaryNodeToLast(firNode,node);
            return String.valueOf(keyHashMap.get(key).y);
        }
    }

    private static void removeFirNode(BinaryNode firNode) {
        firNode.next = firNode.next.next;
    }

    public static void removeTempNode(BinaryNode firNode ,BinaryNode tempNode) {
        while (firNode.next != null) {
            if (firNode.next.x == tempNode.x) {
                firNode.next = firNode.next.next;
                return;
            }
            if (firNode.next.next == null) {
                firNode.next = null;
                return;
            }
        }
    }

    public static void setBinaryNodeToLast(BinaryNode firNode,BinaryNode lastNode) {
        while (firNode.next != null) {
            firNode = firNode.next;
        }
        firNode.next = lastNode;
    }

public class Solution {
   
    //双向链表结点结构
    static class Node {
        int key;
        int val;
        Node pre;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    HashMap<Integer, Node> cache; //缓存结构
    int capacity;//最大容量
    Node head = null;//链表表头
    Node tail = null;//链表表尾

    public Solution(int capacity) {

        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        //判断缓存是否存在这个key
        if (cache.containsKey(key)) {
            //将访问的元素添加到双向链表的表头
            //添加表头元素
            Node cur = cache.get(key);
            //判断该元素是否是表头元素
            if (cur != head) {  //表头元素不移动
                cur.pre.next = cur.next;

                if (cur.next != null)//表尾元素移动需要修改尾部指针
                    cur.next.pre = cur.pre;
                else tail = cur.pre;//说明是表尾元素
                //将元素设为表头元素
                head.pre = cur;
                cur.next = head;
                cur.pre = null;
                head = cur;
            }
            return cache.get(key).val;
        }
        //没有就返回-1
        return -1;
    }

    public void set(int key, int value) {
        //如果是缓存里面的第一个元素
        if (head == tail && head == null) {

            Node cur = new Node(key, value); //构造链表结点
            cache.put(key, cur); //将结点加入缓存
            head = cur;//表头表尾指向该结点
            tail = cur;
        } else {
            //将新添加的元素加入表头
            Node cur = null;
            if (cache.containsKey(key)) {//如果缓存里有key，则更新该key的value值
                cur = cache.get(key);
                cur.val = value;
            } else {
                cur = new Node(key, value);
                if (capacity ==
                        cache.size()) { //如果缓存溢出,删除表尾元素，并将新元素添加进表头
                    //删除表尾元素
                    cache.remove(tail.key);
                    tail = tail.pre;
                    tail.next = null;

                }
            }
            cache.put(key, cur);//将新元素放入缓存
            //添加表头元素
            head.pre = cur;
            cur.next = head;
            head = cur;

        }
    }
}

//标着困难没想到出奇的简单
import java.util.*;
class Node {
    int key = 0;
    int value = 0;
    Node next = null;
}

public class Solution {
    int n = 0;
    int capacity;
    LinkedList<Node> list = new LinkedList<>();
    public Solution(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        int a;
        if (find(key) == -1) return -1;
        else {
            a = list.get(find(key)).value;
            Node node = list.get(find(key));
            list.remove(find(key));
            list.addFirst(node);
            return a;
        }
    }

    public void set(int key, int value) {
        n++;
        if (n > capacity) {
            list.removeLast();
        }
        if (find(key) == -1) {
            Node node = new Node();
            node.key = key;
            node.value = value;
            list.addFirst(node);
        } else {
            list.get(find(key)).value = value;
        }
    }
    public int find(int key) {
        for (int i = 0 ; i < list.size(); i++) {
            if (list.get(i).key == key) return i;
        }
        return -1;
    }
}

import java.util.*;

public class Solution {
    class Node {
        public int key;
        public int val;
        public Node pre;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }

    private HashMap<Integer, Integer> entity;
    private Node head;
    private Node tail;
    private int capacity;
    private int size;

    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        this.size = 0;
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        this.head.next = this.tail;
        this.tail.pre = this.head;
        this.entity = new HashMap<>();
    }

    public int get(int key) {
        // write code here
        Integer val = entity.get(key);
        if (val == null) {
            return -1;
        }

        removeNode(key, val);
        insertHead(new Node(key, val));

        return val;
    }

    public void set(int key, int value) {
        // write code here
        Integer oldVal = entity.put(key, value);
        if (oldVal == null) {
            if (this.size == this.capacity) {
                removeLast();
            } else {
                this.size++;
            }
        }

        if (oldVal != null) {
            removeNode(key, oldVal);
            this.entity.remove(key, oldVal);
        }

        insertHead(new Node(key, value));
    }

    private void removeNode(int key, int val) {
        if (this.size == 0) {
            return;
        }

        Node node = this.head.next;
        while (node != null) {
            if (node.key == key && node.val == val) {
                Node pre = node.pre;
                Node next = node.next;
                pre.next = next;
                next.pre = pre;
                break;
            } else {
                node = node.next;
            }
        }
    }

    private void insertHead(Node node) {
        Node tmp = this.head.next;
        node.next = tmp;
        tmp.pre = node;
        node.pre = this.head;
        this.head.next = node;
    }

    private void removeLast() {
        if (this.size == 0) {
            return;
        }

        Node node = this.tail.pre;
        Node pre = node.pre;
        pre.next = this.tail;
        this.tail.pre = pre;
        node.next = null;
        node.pre = null;
        this.entity.remove(node.key, node.val);
    }
}

import java.util.*;


public class Solution {
    class DLinkedNode{
        int key,value;
        DLinkedNode pre,next;
        public DLinkedNode(){}
        public DLinkedNode(int key1,int value1){
            key=key1;
            value=value1;
        }
    }
    int size,capacity;
    Map<Integer,DLinkedNode> map=new HashMap<Integer,DLinkedNode>();
    DLinkedNode dummyhead,dummytail;
    
    
    public Solution(int capacity) {
        this.size=size;
        this.capacity=capacity;
        dummyhead=new DLinkedNode();
        dummyhead=new DLinkedNode();
        dummyhead.next=dummytail;
        dummytail.pre=dummyhead;
         // write code here
    }

    public int get(int key) {
         // write code here
        if(map.containsKey(key)){
            DLinkedNode node=map.get(key);
            moveTohead(node);
            return node.value;
        }else{return -1;}
    }

    public void set(int key, int value) {
         // write code here
        if(map.containsKey(key)){
            DLinkedNode node=map.get(key);
            moveTohead(node);
            node.value=value;
        }else{
            DLinkedNode node=new DLinkedNode(key,value);
            addTohead(node);
            size=size+1;
            if(size>capacity){
                DLinkedNode tail=dummytail.pre;
                removeNode(tail);
                size=size-1;
                map.remove(tail.key);
            }
        }
    }
    public void addTohead(DLinkedNode node){
        node.pre=dummyhead;
        node.next=dummyhead.next;
        dummyhead.next.pre=node;
        dummyhead.next=node;
    }
    public void removeNode(DLinkedNode node){
        node.next.pre=node.pre;
        node.pre.next=node.next;
    }
    public void moveTohead(DLinkedNode node){
        removeNode(node);
        addTohead(node);
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */