题解 | 设计LRU缓存结构

import java.util.*;


public class Solution {
    int capacity;
    int size;
    int[] keys;
    HashMap<Integer, Integer> map = new HashMap<>();
    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        keys = new int[capacity + 1];
        size = 0;
    }
    public int get(int key) {
        if (size < 1) {
            return -1;
        }

        int res = -1;
        if (map.containsKey(key)) {
            //1.把res值设为value； 2.把keys数组中的key移到末尾
            res = map.get(key);
            toTail(key);
        }
        return res;
    }
    public void set(int key, int value) {
        //1.查找map中是否有key
        if (map.containsKey(key)) {
            //2.如果存在，就更新map和keys数组
            map.put(key, value);
            toTail(key);

        } else {
            //3.如果不存在key，就先判断size是否满了,满了就删除map中的key,弹出keys[0]，更新keys[size-1]，再map.put();
            if (size >= capacity) {
                map.remove(keys[0]);
                for (int i = 0; i < size - 1; i++) {
                    keys[i] = keys[i + 1];
                }
                keys[size - 1] = key;
                map.put(key, value);
            } else {
                //没满就map.put()，然后size++，keys[size-1] = key
                map.put(key, value);
                keys[size] = key;
                size++;
            }

        }
    }
    private void toTail(int key) {
        //1.找到key对应的数组下标i； 2.把i之后的数据往前移动；3.数组末尾size-1置为key
        int index = -1;
        for (int i = 0 ; i < size; i++) {
            if (keys[i] == key) {
                index = i;
                break;
            }
        }
        for (int i = index; i < size - 1; i++) {
            keys[i] = keys[i + 1];
        }
        keys[size - 1] = key;
    }
}

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