2022.02.13 - NC003. Design LRU cache structure

1. subject

2. Ideas

(1) HashMap+ queue

• utilize HashMap Store key value pair data , Using queues to control the replacement of data .

3. Code

import java.util.*;

public class Test {
    
    public static void main(String[] args) {
    
    }
}

class Solution {
    
    public int[] LRU(int[][] operators, int k) {
    
        Map<Integer, Integer> map = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        int[] res = new int[operators.length];
        int index = 0;
        for (int i = 0; i < operators.length; i++) {
    
            switch (operators[i][0]) {
    
                case 1:
                    map.put(operators[i][1], operators[i][2]);
                    queue.offer(operators[i][1]);
                    if (queue.size() > k) {
    
                        map.remove(queue.poll());
                    }
                    break;
                case 2:
                    if (map.containsKey(operators[i][1])) {
    
                        res[index++] = map.get(operators[i][1]);
                        queue.remove(operators[i][1]);
                        queue.offer(operators[i][1]);
                    } else {
    
                        res[index++] = -1;
                    }
                    break;
            }
        }
        return Arrays.copyOfRange(res, 0, index);
    }
}