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

用最容易理解的方法，实现LRU、LFU算法

article 2024/9/28 23:50:31

目录

1、LRU

1.1、问题描述：

1.2、解题思路：使用LinkedHashMap实现

2、LFU

2.1、问题描述：

2.2、解题思路：使用LinkedHashMap

1、LRU

1.1、问题描述：

题目：可参考牛客：设计LRU缓存结构_牛客题霸_牛客网

问题概述：实现一个类，这个类需要做以下几件事情：

  • 类实例化后，可以存储key、value的键值对；
  • 存储的键值对数是有限的，当数量达到上限后，就会删除最久未访问过的键值对
  • 实现一个get方法，可以通过key，获取到value的值（这也算是一次访问）
  • 实现一个set方法，可以将key，value存放进去（若key存在，则更新value值）
  • 要求get、set方法的时间复杂度为O(1)

1.2、解题思路：使用LinkedHashMap实现

        首先，我们其实可以理解为，我们现在是需要一个map的，来存储key、value，例如我们可以使用HashMap或者是TreeMap，因为要求get、set方法的时间复杂度为O(1)，所以我们选择HashMap~

        其次呢，我们还要记录map进去的键值对的顺序的，所以很显然，我们可以选择LinkedHashMap。LinkedHashMap的底层其实就是：维护着一个HashMap：key、value在HashMap中存储着；还维护着一个双向链表：key、value在链表中也会有自己的位置 - 维护他的顺序（key、value以Node节点存在，有pre指针、next指针）~

        我们可以进入LinkedHashMap源码中看看：

接下来就是代码实现了，还是很容易理解的：

import java.util.*;


public class Solution {
    LinkedHashMap<Integer, Integer> map;
    int cacapacity = 0;//长度
    int size = 0;
    public Solution(int capacity) {
        // write code here
        this.cacapacity = capacity;
        this.map = new LinkedHashMap<>(capacity);
    }

    public int get(int key) {
        // write code here
        Integer value = map.get(key);
        if(value == null){
            return -1;
        } else {
            map.remove(key);
            map.put(key, value);
            return value;
        }
    }

    public void set(int key, int value) {
        // write code here
        if(map.containsKey(key)){
            map.remove(key);
            map.put(key, value);
        } else {
            if(size < cacapacity){
                map.put(key ,value);
                size++;
            } else if(size == cacapacity){
                int first = map.keySet().iterator().next();
                map.remove(first);
                map.put(key, value);
            }
            
        }
        return;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

2、LFU

2.1、问题描述：

题目：可参考牛客：设计LFU缓存结构_牛客题霸_牛客网

问题概述：实现一个类，这个类需要做以下几件事情：

  • 类实例化后，可以存储key、value的键值对；
  • 存储的键值对数是有限的，当数量达到上限后，就会删除访问次数最少得键值对（访问次数一样，则删除最久未被访问的）
  • 实现一个get方法，可以通过key，获取到value的值（这也算是一次访问）
  • 实现一个set方法，可以将key，value存放进去（若key存在，则更新value值）

2.2、解题思路：使用LinkedHashMap

        首先，我们其实可以理解为，我们现在是需要一个map的，来存储key、value，例如我们可以使用HashMap或者是TreeMap，我们继续选择HashMap~

        其次呢，我们需要对这些键值对进行排序，排序规则：访问次数从小到大排序，访问次数相同时，则按照访问时间从小到大排序，所以很显然，我们可以选择LinkedHashMap。

        思路：

  • 使用LinkedHashMap来维护键值对的存储；
  • 这里存储时，同时还要记录访问次数，因此，我们map中的存储数据格式采用键：key，值：是一个一维数组，数组第一个值是value值，数组第二个值是访问次数的count值；
  • 如果是get，没有则返回-1；有键值对时，记录value值，将原有的键值对删除，调用公共方法再把这个键值加上去，记得count++（公共方法，后面说）；
  • 如果是set：
    • 先查看这个key是否已存在过，如果key之前不存在：
      • 存储的数量未达到上限，键值对的count设为1，调用公共方法新增键值对；
      • 存储的数量达到上限，先删除map中第一个key，再调用公共方法新增这组新的键值对；
    • 如果key之前就存在：先查询到这个key的count，调用公共方法新增键值对（key，新的value，++count）；
  • 公共方法新增键值对：新增键值对的位置要求：访问次数从小到大排序，访问次数相同时，则按照访问时间从小到大排序，思路：
    • 公共方法的参数：原本的LinkedHashMap - 变量map；key、value、count
    • 再准备一个备用的LinkedHashMap - 变量设为res，参数中的LinkedHashMap，变量设为map
    • 遍历map：
      • 如果遍历的count小于等于方法传参中的count，则把这组键值对移到res中
      • 如果遍历的count大于方法传参中的count，则先给res新增一组键值对（方法传参中的键值对），停止遍历
      • 再遍历map剩余的键值对，将他们转移到res中

注意：看着很复杂，其实就是一些判断而已，主要就是遵循排序规则就可以了

代码如下：

import java.util.*;


public class Solution2 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public static int[] LFU (int[][] operators, int k) {
        // write code here
        LinkedHashMap<Integer, int[]> map = new LinkedHashMap<>(k);
        int size = 0;
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0;i<operators.length;i++){
            //opt = 1,set
            if(operators[i][0] == 1){
                // set key:operators[i][1] value:operators[i][2] count:operators - 待定
                int[] tmp = map.get(operators[i][1]);
                //新key
                if(tmp == null){
                    // 满了
                    if(size == k){
                        Integer first = map.keySet().iterator().next();
                        map.remove(first);
                        //新增进去 todo:
                        map = fun(map, operators[i][1], operators[i][2], 1);

                    } else {
                        //todo:
                        map = fun(map, operators[i][1], operators[i][2], 1);
                        size++;
                    }
                } else {
                    //旧key,修改value，count todo:
                    map.remove(operators[i][1]);
                    map = fun(map, operators[i][1], operators[i][2], ++tmp[1]);
                }


            }else {
                // get
                int[] tmp = map.get(operators[i][1]);
                if(tmp == null){
                    res.add(-1);
                } else {
                    //记录value
                    res.add(tmp[0]);
                    //修改次数 todo
                    map.remove(operators[i][1]);
                    map = fun(map, operators[i][1], tmp[0], ++tmp[1]);
                }
            }
        }
        int[] arr = new int[res.size()];
        for(int i = 0;i<res.size();i++){
            arr[i] = res.get(i);
        }
        return arr;

    }
    //插入 - 整个顺序为-先以count排序，count相同时，插入时间顺序排序
    public static LinkedHashMap<Integer, int[]> fun(LinkedHashMap<Integer, int[]> map, int key , int value, int count){
        LinkedHashMap<Integer, int[]> res = new LinkedHashMap<>();
        int size = 0;
        int mapSize = map.size();
        while (size<mapSize){
            int first = map.keySet().iterator().next();
            int[] arr = map.get(first);
            if(arr[1] <= count){
                res.put(first, arr);
                map.remove(first);
            } else {
                int[] tmp = new int[]{value, count};
                res.put(key, tmp);
                break;
            }
            size++;
        }
        while (size<mapSize){
            int first = map.keySet().iterator().next();
            int[] arr = map.get(first);
            res.put(first, arr);
            map.remove(first);
            size++;
        }
        //检查新增的key是否成功新增了，如果没有在把他新增在最后面（例如：这组键值对的count最大，就应该在最后一个）
        if(map.get(key) == null){
            int[] tmp = new int[]{value, count};
            res.put(key, tmp);
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {{1,1,1},{1,2,2},{1,3,3},{1,4,4},{2,4},{2,3},{2,2},{2,1},{1,5,5},{2,4}};
//        int[][] arr ={{1,1,1},{1,2,2},{2,2}};
        LFU(arr, 4);
    }
}


http://www.kler.cn/news/323838.html

相关文章：

  • 代码随想录训练营第45天|编辑距离
  • 微前端框架之乾坤【qiankun】（一）
  • 使用SSE流式输出（Javaweb前后端实战）
  • 测试用例的进阶二
  • 速盾：视频开cdn合适还是视频点播合适？
  • cv2.waitkey(30) 按键盘无效
  • 快速排序(plus）与单调栈道，力扣912.排序数组​​​​​​​力扣215.数组中的第k大个元素力扣17.14最小的k个数单调栈力扣.柱状图中最大的矩形
  • OpenHarmony标准系统上实现对rk系列芯片NPU的支持(npu使用)
  • LORA DASH -一种更高效的微调方式
  • python医疗机器人手术
  • html TAB切换按钮变色、自动生成table--使用函数优化结构
  • opencv：实现图像的自动裁剪与优化
  • Python中的机器学习：从入门到实战
  • GO入门核心基础
  • 【linux 多进程并发】linux下使用常见命令，来解析进程家族体系脉络
  • Java: 数据类型与变量和运算符
  • 网络管理：网络故障排查指南
  • 目前相对稳定的下载上传的方法（WebClient ）（异步与进度）
  • MacOS Sequoia安装geant4.10.07
  • 20_BERT微调训练
  • 探索Python网络世界的利器：Requests-HTML库
  • Python自学查漏9.28
  • Spark 中 任务集 TaskSet 详解
  • 探索私有化聊天软件：即时通讯与音视频技术的结合
  • RSpec简析及应用案例
  • leetcode刷题day32|动态规划Part01（509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯）
  • uni-app进行微信小程序开发，快速上手
  • STM32 F1移植FATFS文件系统 USMART组件测试相关函数功能
  • 二、初步编写drf API
  • 太速科技-389-基于KU5P的双路100G光纤网络加速计算卡