題目描述

設計LRU緩存結構，該結構在構造時確定大小，假設大小為K，并有如下兩個功能

• set(key, value)：將記錄(key, value)插入該結構
• get(key)：返回key對應的value值

[要求]

set和get方法的時間復雜度為O(1)

某個key的set或get操作一旦發生，認為這個key的記錄成了最常使用的。

當緩存的大小超過K時，移除最不經常使用的記錄，即set或get最久遠的。

若opt=1，接下來兩個整數x, y，表示set(x, y)
若opt=2，接下來一個整數x，表示get(x)，若x未出現過或已被移除，則返回-1
對于每個操作2，輸出一個答案

?

示例1

輸入

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

返回值

[1,-1]

說明

第一次操作后：最常使用的記錄為("1", 1) 第二次操作后：最常使用的記錄為("2", 2)，("1", 1)變為最不常用的 第三次操作后：最常使用的記錄為("3", 2)，("1", 1)還是最不常用的 第四次操作后：最常用的記錄為("1", 1)，("2", 2)變為最不常用的 第五次操作后：大小超過了3，所以移除此時最不常使用的記錄("2", 2)，加入記錄("4", 4)，并且為最常使用的記錄，然后("3", 2)變為最不常使用的記錄

?

import java.util.*;public class TestLRU {public static void main(String[] args) {// [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3int [][] data = new int[][]{{1,1,1},{1,2,2},{1,3,2},{2,1},{1,4,4},{2,2}};TestLRU testLRU = new TestLRU();int [] result = testLRU.LRU(data,3);System.out.println(Arrays.toString(result));}/*** lru design* @param operators int整型二維數組 the ops* @param k int整型 the k* @return int整型一維數組*/public int[] LRU (int[][] operators, int k) {LinkedHashMap<Integer,Integer> lruM = new LinkedHashMap<>();List<Integer> restList = new ArrayList<Integer>();for(int[] operator : operators){switch(operator[0]){case 1:if(lruM.size() >= k){// 緩存已經存滿// 當緩存的大小超過K時，移除最不經常使用的記錄，即set或get最久遠的。Iterator<Integer> iterator = lruM.keySet().iterator();lruM.remove(iterator.next());lruM.put(operator[1],operator[2]);}else{lruM.put(operator[1],operator[2]);}break;case 2:if(!lruM.isEmpty() && lruM.containsKey(operator[1])){// 某個key的set或get操作一旦發生，認為這個key的記錄成了最常使用的Integer value = lruM.get(operator[1]);lruM.remove(operator[1]);lruM.put(operator[1],value); // 設置為最新restList.add(value);}else{restList.add(-1);}break;}}int[] resutArr = new int[restList.size()];int i = 0;for(Integer value : restList){resutArr[i++] = value;}return resutArr;}}

?

總結

以上是生活随笔為你收集整理的常考数据结构和算法:设计LRU缓存结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。