题解 | #LRU Cache#

解题思路：

最近访问的元素放在第一个，其他的往后挪，可以用双向链表LinkedList来实现

需要实现两个方法：put和get

• get的时候需要调整优先级，要把当前访问的item移到第一个
• put需要实现更新/增加/替换的操作
• 更新：key已经存在的情况，找到对应的item，更新value
• 增加：key不存在，cache没有满，即cache size小于capacity，那么直接将它加到第一个
• 替换：key不存在，cache满了，即cache size等于capacity，那么要将最后一个元素删除，然后将当前的item加入到第一个

put和get都有查找findEntryByKey操作，时间复杂度是O(n)，如果要优化成O(1)的话，需要用哈希表来存储key对应的KeyValue

import java.util.Scanner;
import java.util.*;

public class Main {
    private static LinkedList<KeyValue> cache = new LinkedList<KeyValue>();
    private static Map<Integer, KeyValue> lookUp = new HashMap<Integer, KeyValue>();
    private static int capacity = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextLine()) {
            String[] input = in.nextLine().split(" ");
            if (input.length == 1) {
                capacity = Integer.valueOf(input[0]);
                continue;
            }

            if (input.length == 2) {
                handleGetCommand(input);
            }

            if (input.length == 3) {
                handlePushCommand(input);
            }
        }
    }

    private static void handleGetCommand(String[] input) {
        int key = Integer.valueOf(input[1]);
        KeyValue target = findEntryByKey(key);
        if (target == null) {
            System.out.println("-1");
            return;
        }
        int index = cache.indexOf(target);
        ajustPriority(index);
        System.out.println(target.getValue());
    }

    private static void handlePushCommand(String[] input) {
        int key = Integer.valueOf(input[1]);
        int value = Integer.valueOf(input[2]);

        KeyValue target = findEntryByKey(key);

        if (target != null) {
            int index = cache.indexOf(target);
            cache.get(index).setValue(value);
            lookUp.get(key).setValue(value);
            return;
        }

        if (capacity < 1) {
            return;
        }

        if (cache.size() == capacity) {
            KeyValue toRemove = cache.getLast();
            lookUp.remove(toRemove.key);
            cache.remove(toRemove);
        }
        KeyValue newItem = new KeyValue(key, value);
        cache.addFirst(newItem);
        lookUp.put(key, newItem);
    }

    private static KeyValue findEntryByKey(int key) {
        return lookUp.get(Integer.valueOf(key));
    }

    private static void ajustPriority(int index) {
        KeyValue target = cache.get(index);
        cache.remove(target);
        cache.addFirst(target);
    }

    private static class KeyValue {
        private int key;
        private int value;
        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getKey() {
            return key;
        }

        public KeyValue(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

}