首页 > 每天刷一道牛客题霸-第2天-设计LRU缓存结构
头像
菜鸟也要飞的高
编辑于 2020-12-01 14:25
+ 关注

每天刷一道牛客题霸-第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);
     }
    }

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐