LeetCode-460. LFU 缓存【设计 哈希表 链表 双向链表】

LeetCode-460. LFU 缓存【设计 哈希表 链表 双向链表】

  • 题目描述：
  • 解题思路一：一张图秒懂 LFU！
  • 解题思路二：精简版！两个哈希表，一个记录所有节点，一个记录次数链表【defaultdict(new_list)，只是记录虚拟节点，会自动创建】。双链表实现多了一个freq，同时维护一个min_freq，每次删除节点的时候都要维护记录次数链表和min_freq。注意当节点超出容量的时候在self.freq_to_dummy[self.min_freq]里面删除尾部节点。
  • 解题思路三：精简

题目描述：

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。
为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入：
[“LFUCache”, “put”, “put”, “get”, “put”, “get”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // 返回 -1（未找到）
lfu.get(3); // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // 返回 -1（未找到）
lfu.get(3); // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3

提示：

1 <= capacity <= 104
0 <= key <= 105
0 <= value <= 109
最多调用 2 * 105 次 get 和 put 方法

LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】, 这两题是十分相似的。！

解题思路一：一张图秒懂 LFU！

在这里插入图片描述

class Node:
    # 提高访问属性的速度，并节省内存
    __slots__ = 'prev', 'next', 'key', 'value', 'freq'

    def __init__(self, key=0, val=0):
        self.key = key
        self.value = val
        self.freq = 1  #  新书只读了一次

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = dict()
        def new_list() -> Node:
            dummy = Node()  # 哨兵节点
            dummy.prev = dummy
            dummy.next = dummy
            return dummy
        self.freq_to_dummy = defaultdict(new_list)

    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.key_to_node:  # 没有这本书
            return None
        node = self.key_to_node[key]  # 有这本书
        self.remove(node)  # 把这本书抽出来
        dummy = self.freq_to_dummy[node.freq]
        if dummy.prev == dummy:  # 抽出来后，这摞书是空的
            del self.freq_to_dummy[node.freq]  # 移除空链表
            if self.min_freq == node.freq:  # 这摞书是最左边的
                self.min_freq += 1
        node.freq += 1  # 看书次数 +1
        self.push_front(self.freq_to_dummy[node.freq], node)  # 放在右边这摞书的最上面
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:  # 有这本书
            node.value = value  # 更新 value
            return
        if len(self.key_to_node) == self.capacity:  # 书太多了
            dummy = self.freq_to_dummy[self.min_freq]
            back_node = dummy.prev  # 最左边那摞书的最下面的书
            del self.key_to_node[back_node.key]
            self.remove(back_node)  # 移除
            if dummy.prev == dummy:  # 这摞书是空的
                del self.freq_to_dummy[self.min_freq]  # 移除空链表
        self.key_to_node[key] = node = Node(key, value)  # 新书
        self.push_front(self.freq_to_dummy[1], node)  # 放在「看过 1 次」的最上面
        self.min_freq = 1

    # 删除一个节点（抽出一本书）
    def remove(self, x: Node) -> None:
        x.prev.next = x.next
        x.next.prev = x.prev

    # 在链表头添加一个节点（把一本书放在最上面）
    def push_front(self, dummy: Node, x: Node) -> None:
        x.prev = dummy
        x.next = dummy.next
        x.prev.next = x
        x.next.prev = x

时间复杂度：O(1)
空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。

解题思路二：精简版！两个哈希表，一个记录所有节点，一个记录次数链表【defaultdict(new_list)，只是记录虚拟节点，会自动创建】。双链表实现多了一个freq，同时维护一个min_freq，每次删除节点的时候都要维护记录次数链表和min_freq。注意当节点超出容量的时候在self.freq_to_dummy[self.min_freq]里面删除尾部节点。

from collections import defaultdict
class DLinkNode:
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
        self.freq = 1

class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = dict()
        def new_DLinkList():
            dummy = DLinkNode()
            dummy.next = dummy
            dummy.prev = dummy
            return dummy
        self.freq_to_dummy = defaultdict(new_DLinkList)

    def get_node(self, key):
        if key not in self.key_to_node:
            return None
        node = self.key_to_node[key]
        self.remove(node)
        dummy = self.freq_to_dummy[node.freq]
        if dummy.prev == dummy:
            del self.freq_to_dummy[node.freq]
            if self.min_freq == node.freq:
                self.min_freq += 1
        node.freq += 1
        self.push_front(self.freq_to_dummy[node.freq], node)
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value
            return 
        node = DLinkNode(key, value) # 一定是新的，要在插入前空出位置
        if len(self.key_to_node) == self.capacity:
            dummy = self.freq_to_dummy[self.min_freq]
            tail = dummy.prev
            del self.key_to_node[tail.key]
            self.remove(tail)
            if dummy.prev == dummy:
                del self.freq_to_dummy[tail.freq]
        self.key_to_node[key] = node
        self.push_front(self.freq_to_dummy[1], node)
        self.min_freq = 1
        

    def remove(self, x):
        x.next.prev = x.prev
        x.prev.next = x.next
    
    def push_front(self, dummy, x):
        x.next = dummy.next
        x.prev = dummy
        x.prev.next = x
        x.next.prev = x

# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

时间复杂度：O(1)
空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。

解题思路三：精简

from collections import defaultdict
class DLinkNode:
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
        self.freq = 1

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = {}
        def make_dummy():
            dummy = DLinkNode()
            dummy.next = dummy
            dummy.prev = dummy
            return dummy
        self.freq_to_dummy = defaultdict(make_dummy)

    def get_node(self, key):
        if key not in self.key_to_node:
            return None
        node = self.key_to_node[key]
        self.remove(node)
        dummy = self.freq_to_dummy[node.freq]
        if dummy.prev == dummy:
            del self.freq_to_dummy[node.freq]
            if self.min_freq == node.freq:
                self.min_freq += 1
        node.freq += 1
        dummy = self.freq_to_dummy[node.freq]
        self.push_front(dummy, node)
        return node # 记得返回

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value
            return 
        node = DLinkNode(key, value) # 新节点，先给位置再插入
        if len(self.key_to_node) == self.capacity:
            dummy = self.freq_to_dummy[self.min_freq]
            tail = dummy.prev
            self.remove(tail)
            del self.key_to_node[tail.key]
            if dummy.prev == dummy:
                del self.freq_to_dummy[tail.freq]
        # 维护两个链表和min_freq
        self.key_to_node[key] = node
        dummy = self.freq_to_dummy[1]
        self.push_front(dummy, node)
        self.min_freq = 1

    def remove(self, x):
        x.next.prev = x.prev
        x.prev.next = x.next

    def push_front(self, dummy, x):
        x.next = dummy.next
        x.prev = dummy
        x.prev.next = x
        x.next.prev = x

# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

时间复杂度：O(1)
空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。

创作不易，观众老爷们请留步… 动起可爱的小手，点个赞再走呗 (๑◕ܫ￩๑)
欢迎大家关注笔者，你的关注是我持续更博的最大动力


原创文章，转载告知，盗版必究

在这里插入图片描述

在这里插入图片描述
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/619197.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

kafka安装配置及集成springboot

kafka安装配置及集成springboot

1. 安装 单机安装kafka Kafka对于zookeeper是强依赖&#xff0c;保存kafka相关的节点数据&#xff0c;所以安装Kafka之前必须先安装zookeeper dockerhub网址: https://hub.docker.com Docker安装zookeeper 下载镜像&#xff1a; docker pull zookeeper:3.4.14创建容器 doc…
阅读更多...
SeetaFace6人脸活体检测C++代码实现Demo

SeetaFace6人脸活体检测C++代码实现Demo

SeetaFace6包含人脸识别的基本能力&#xff1a;人脸检测、关键点定位、人脸识别&#xff0c;同时增加了活体检测、质量评估、年龄性别估计&#xff0c;并且顺应实际应用需求&#xff0c;开放口罩检测以及口罩佩戴场景下的人脸识别模型。 官网地址&#xff1a;https://github.co…
阅读更多...
【CSP CCF记录】数组推导

【CSP CCF记录】数组推导

题目 过程 思路 每次输入一个Bi即可确定一个Ai值&#xff0c;用temp记录1~B[i-1]&#xff0c;的最大值分为两种情况&#xff1a; 当temp不等于Bi时&#xff0c;则说明Bi值之前未出现过&#xff0c;Ai必须等于Bi才能满足Bi是Ai前缀最大的定义。当temp等于Bi时&#xff0c;则说…
阅读更多...
后端开发之用Mybatis简化JDBC的开发快速入门2024及数据库连接池技术和lombok工具详解

后端开发之用Mybatis简化JDBC的开发快速入门2024及数据库连接池技术和lombok工具详解

JDBC 简化JDBC的开发 JDBC仅仅是一套接口 是一套规范 Mybatis是持久层框架 用于简化JDBC的开发 使用Java语言操作关系型数据库的一套API 原始的JDBC程序 package com.bigdate.mybatis;import com.bigdate.mybatis.mapper.UserMapper; import com.bigdate.mybatis.pojo.Use…
阅读更多...
（二）Jetpack Compose 布局模型

（二）Jetpack Compose 布局模型

前文回顾 &#xff08;一&#xff09;Jetpack Compose 从入门到会写-CSDN博客 首先让我们回顾一下上一篇文章中里提到过几个问题&#xff1a; ComposeView的层级关系&#xff0c;互相嵌套存在的问题&#xff1f; 为什么Compose可以实现只测量一次&#xff1f; ComposeView和…
阅读更多...
【JVM】感觉弗如...类加载机制

【JVM】感觉弗如...类加载机制

【JVM】感觉弗如…类加载机制 在Java开发过程中&#xff0c;从源代码&#xff08;.java文件&#xff09;到字节码&#xff08;.class文件&#xff09;再到运行时的类加载&#xff0c;会经历几个关键步骤&#xff0c;我们先简单过一遍大体的过程。再介绍今天这篇博客的重点内容—…
阅读更多...
几个字符串函数的使用和模拟实现（2）

几个字符串函数的使用和模拟实现（2）

strcop的使用和模拟实现 strcpy函数的使用事项&#xff1a; 源字符串时不需要修改的&#xff0c;在定义前加上const 源字符串被拷贝到目标字符串上时终止字符\0也被拷贝进去 目标数组的大小要相对于源数组的大小足够大&#xff0c;并且不应该在内存中重叠 函数的返回值是一个字…
阅读更多...
【Unity】Unity项目转抖音小游戏（二）云数据库和云函数

【Unity】Unity项目转抖音小游戏（二）云数据库和云函数

业务需求&#xff0c;开始接触一下抖音小游戏相关的内容&#xff0c;开发过程中记录一下流程。 抖音云官方文档&#xff1a;https://developer.open-douyin.com/docs/resource/zh-CN/developer/tools/cloud/develop-guide/cloud-function-debug 1.开通抖音云环境 抖音云地址&a…
阅读更多...
软件体系结构风格

软件体系结构风格

目录 一、定义 二、.经典软件体系结构风格&#xff1a; 1.管道和过滤器 2.数据抽象和面向对象系统 3.基于事件系统&#xff08;隐式调用&#xff09; 4.分层系统 5.仓库 6.C2风格 7.C/S 8.三层C/S 9.B/S 题&#xff1a; 一、定义 软件体系机构风格是描述某一特定应用…
阅读更多...
C#泛型委托

C#泛型委托

在C#中&#xff0c;delegate 关键字用于声明委托&#xff08;delegates&#xff09;&#xff0c;委托是一种类型安全的函数指针&#xff0c;允许你传递方法作为参数或从方法返回方法。有时我们需要将一个函数作为另一个函数的参数&#xff0c;这时就要用到委托&#xff08;Dele…
阅读更多...
java项目之车辆管理系统(springboot+vue+mysql)

java项目之车辆管理系统(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的车辆管理系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 车辆管理系统的主要使用者分…
阅读更多...
Deckset for Mac：让演示文稿制作更轻松

Deckset for Mac：让演示文稿制作更轻松

还在为繁琐的演示文稿制作而烦恼吗&#xff1f;Deckset for Mac来帮您解决&#xff01;它支持Markdown语言&#xff0c;让您只需专注于内容的创作&#xff0c;无需在排版和设计上耗费过多精力。丰富的主题和布局选项&#xff0c;让您能够轻松打造出专业级的演示文稿。快来体验D…
阅读更多...
云计算第十二课

云计算第十二课

安装虚拟机 第一步新建虚拟机 选择自定义安装 下一步 选择稍后安装操作系统 选择系统类型和版本 选择虚拟机文件路径&#xff08;建议每台虚拟机单独存放并且路径不要有中文&#xff09;点击下一步 选择bios下一步 选择虚拟机处理器内核数量 默认硬盘或者自行调大硬盘 选择虚…
阅读更多...
软件测试的分类

软件测试的分类

1.用户分类 2.查看代码分类 3.阶段分类
阅读更多...
云计算十三课

云计算十三课

centos安装 点击左上角文件 点击新建虚拟机 点击下一步 点击稍后安装操作系统&#xff0c;下一步 选择Linux&#xff08;l&#xff09;下一步 设置虚拟机名称 点击浏览选择安装位置 新建文件夹设置名称不能为中文&#xff0c;点击确定 点击下一步 设置磁盘大小点击下一步…
阅读更多...
4.1 编写程序，从键盘接收一个小写字母，然后找出他的前导字符和后续字符，再按顺序显示这三个字符

4.1 编写程序，从键盘接收一个小写字母，然后找出他的前导字符和后续字符，再按顺序显示这三个字符

方法一&#xff1a; 运行效果&#xff1a; 输入B&#xff0c;输出显示ABC&#xff1b;输入A&#xff0c;输出显示AB 思路&#xff1a; 1、通过键盘输入接收一个字母。 2、将输入的字母减去1&#xff0c;得到前导字符&#xff0c;然后输出。 3、将输入的字母加上1&#xff0c;得…
阅读更多...
【python量化交易】qteasy使用教程07——创建更加复杂的自定义交易策略

【python量化交易】qteasy使用教程07——创建更加复杂的自定义交易策略

创建更加复杂的自定义交易策略 使用交易策略类&#xff0c;创建更复杂的自定义策略开始前的准备工作本节的目标继承Strategy类&#xff0c;创建一个复杂的多因子选股策略策略和回测参数配置&#xff0c;并开始回测 本节回顾 使用交易策略类&#xff0c;创建更复杂的自定义策略 …
阅读更多...
（四十）第 6 章 树和二叉树（树的双亲表存储）

（四十）第 6 章 树和二叉树（树的双亲表存储）

1. 背景说明 2. 示例代码 1) errorRecord.h // 记录错误宏定义头文件#ifndef ERROR_RECORD_H #define ERROR_RECORD_H#include <stdio.h> #include <string.h> #include <stdint.h>// 从文件路径中提取文件名 #define FILE_NAME(X) strrchr(X, \\) ? strrch…
阅读更多...
基于yolov5+streamlit目标检测演示系统设计

基于yolov5+streamlit目标检测演示系统设计

YOLOv5与Streamlit&#xff1a;智能目标检测可视化展示介绍 随着人工智能技术的飞速发展&#xff0c;目标检测技术已成为推动智能化社会进步的关键技术之一。在众多目标检测算法中&#xff0c;YOLOv5以其卓越的性能和实时性&#xff0c;成为了业界的佼佼者。与此同时&#xff…
阅读更多...
代码随想录阅读笔记-动态规划【爬楼梯】

代码随想录阅读笔记-动态规划【爬楼梯】

题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 注意&#xff1a;给定 n 是一个正整数。 示例 1&#xff1a; 输入&#xff1a; 2输出&#xff1a; 2解释&#xff1a; 有两种方法可以爬到楼…
阅读更多...
最新文章

Copyright @ 2022~2023