每天刷一道牛客题霸-第2天-设计LRU缓存结构

题目

https://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61?tpId=190&&tqId=35214&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking

基本思路

使用Map做hash映射,使用队列做先进先出

1. Go语言

   package main
   func LRU( operators [][]int ,  k int ) []int {
    var list []int
    var result []int
    containMap := make(map[int]int)
    for _,item:= range operators{
        if item[0] == 1 {
            if _ ,ok :=containMap[item[1]];ok {
                for i,value := range list{
                    if value == item[1] {
                        list = append(list[:1], list[2:]...)
                        i--
                    }
                }
            }
            if len(list) >= k {
                key := list[0]
                delete(containMap, key)
                list = list[1:]
            }
            containMap[item[1]] = item[2]
            list = append(list, item[1])
        }else if item[0] == 2 {
            _,ok := containMap[item[1]]
            if ok {
                if _ ,ok :=containMap[item[1]];ok {
                    for i,value := range list{
                        if value == item[1] {
                            list = append(list[:i], list[i+1:]...)
                            i--
                        }
                    }
                }
                list = append(list, item[1])
                result = append(result, containMap[item[1]])
            }else {
                result = append(result,-1)
            }
        }
    }
    return result
   }

2. Java

   import java.util.*;
   public class Solution {
    public static int[] LRU (int[][] operators, int k) {
        // write code here
        LinkedList<Integer> list = new LinkedList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        ArrayList<Integer> resultList = new ArrayList<>();
        for (int i = 0 ; i < operators.length ; i++){
            Integer[] value = new Integer[2];
   
            if (operators[i][0] == 1){
                value[0] = operators[i][1];
                value[1] = operators[i][2];
                if (list.size() >= k){
                    Integer removeValue = list.removeFirst();
                    map.remove(removeValue);
                }
                list.add(value[0]);
                map.put(operators[i][1],operators[i][2]);
            }else  {
                if (map.containsKey(operators[i][1])) {
                    int mapValue = map.get(operators[i][1]);
                    value[0] = operators[i][1];
                    value[1] = mapValue;
                    list.remove(value[0]);
                    list.add(value[0]);
                    resultList.add(mapValue);
                }else {
                    resultList.add(-1);
                }
            }
        }
        int[] resultArray = new int[resultList.size()];
        for (int i = 0 ; i < resultArray.length ; i++){
            resultArray[i] = resultList.get(i);
        }
        return resultArray;
    }
   
    public static void main(String[] args) {
        int[][] arr = {
                {1,1,1},
                {1,2,2},
                {1,3,2},
                {2,1},
                {1,4,4},
                {2,2}
        };
        LRU(arr,3);
    }
   }