当前位置：首页 > news >正文

链表-设计LRU缓存结构

news 来源：原创 2024/9/29 13:21:28

题目描述：

代码实现：这里记录了根据LRU算法原理最直接理解的代码实现。

import java.util.*;//存储输入内容，记录访问权值
class CounterInfo {int key;int value;int times;//代表key对应的权值，值越小优先级越高public CounterInfo(int key, int value) {this.key = key;this.value = value;this.times = 0;}
}public class Solution {ArrayList<CounterInfo> intarr;int maxsize;public Solution(int capacity) {// write code hereintarr = new ArrayList<CounterInfo>(0);this.maxsize = capacity;}//除了key以外的元素都更新times++public void refreshTimes(int key) {Iterator infoit = intarr.iterator();while (infoit.hasNext()) {CounterInfo nowinfo = (CounterInfo)infoit.next();if (nowinfo.key != key) {nowinfo.times++;}}}/*1.遍历列表看是否存在key，如果存在则返回相应的value，如果不存在返回-12.如果存在目标key，并且目标key对应权值不为0，更新目标key对应的权值为0，其他key对应权值都+13.如果存在目标key，但是目标key对应权值为0，列表内所有权值不做改变*/public int get(int key) {boolean isfind = false;boolean isrefresh = false;int resValue = -1;//查找intarr中是否存在keyIterator infoit = intarr.iterator();while (infoit.hasNext()) {CounterInfo nowinfo = (CounterInfo)infoit.next();if (nowinfo.key == key) {isfind = true;resValue = nowinfo.value;if (nowinfo.times != 0) {isrefresh = true;nowinfo.times = 0;} else {isrefresh = false;}}}if (isfind) {if (isrefresh) {//更新其他info的timesthis.refreshTimes(key);}return resValue;} else {return -1;}}/*1.看是否存在key，如果存在更新key对应的value和权值=02.如果不存在：2.1 列表满：选择权值最大的元素，修改key，value，权值=0；其他元素权值+12.2 列表未满：列表添加新的CounterInfo对象；其他元素权值+1*/public void set(int key, int value) {//先看是否存在boolean isfind = false;//查找intarr中是否存在keyIterator infoit = intarr.iterator();while (infoit.hasNext()) {CounterInfo nowinfo = (CounterInfo)infoit.next();if (nowinfo.key == key) {isfind = true;//更新valuenowinfo.value = value;if (nowinfo.times != 0) {nowinfo.times = 0;this.refreshTimes(key);}}}if (!isfind) {//判断是否达到最大长度if (intarr.size() == maxsize) {//找到最久未访问的元素，更新key，value，timesinfoit = intarr.iterator();//找到最大timeint maxtime = 0;while (infoit.hasNext()) {CounterInfo nowinfo = (CounterInfo)infoit.next();maxtime = maxtime > nowinfo.times ? maxtime : nowinfo.times;}//根据最大time更新key-value值infoit = intarr.iterator();while (infoit.hasNext()) {CounterInfo nowinfo = (CounterInfo)infoit.next();if (nowinfo.times == maxtime) {nowinfo.times = 0;nowinfo.key = key;nowinfo.value = value;}}} else {CounterInfo newinfo = new CounterInfo(key, value);intarr.add(newinfo);}this.refreshTimes(key);}}
}/*** Your Solution object will be instantiated and called as such:* Solution solution = new Solution(capacity);* int output = solution.get(key);* solution.set(key,value);*/

刷题链接：

设计LRU缓存结构_牛客题霸_牛客网