[146 LRU缓存](https://leetcode.cn/problems/lru-cache/)

分析

维护一个双向链表保存缓存中的元素。
如果元素超过容量阈值,则删除最久未使用的元素。为了实现这个功能,将get(), put()方法获取的元素添加到链表首部。
为了在O(1)时间复杂度执行get()方法,再新建一个映射表,缓存key与链表节点。

源码

class LRUCache {private int size;private int capacity;private Map<Integer, Node> cache = new HashMap<>();private Node head;private Node tail;public LRUCache(int capacity) {this.capacity = capacity;this.size = 0;this.head = new Node();this.tail = new Node();this.head.next = this.tail;this.tail.prev = this.head;}public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}moveToHead(node);return node.value;}public void put(int key, int value) {Node node = cache.get(key);if (node == null) {node = new Node(key, value);cache.put(key, node);addToHead(node);size++;if (size > capacity) {Node tail = removeTail();cache.remove(tail.key);size--;}}node.value = value;moveToHead(node);}private void addToHead(Node node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(Node node) {removeNode(node);addToHead(node);}private Node removeTail() {Node res = tail.prev;removeNode(res);return res;}class Node {int key;int value;Node prev;Node next;public Node(int key, int value) {this.key = key;this.value = value;}public Node() {}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Spark执行计划解析后是如何触发执行的?

在前一篇Spark SQL 执行计划解析源码分析中&#xff0c;笔者分析了Spark SQL 执行计划的解析&#xff0c;很多文章甚至Spark相关的书籍在讲完执行计划解析之后就开始进入讲解Stage切分和调度Task执行&#xff0c;每个概念之间没有强烈的关联&#xff0c;因此这中间总感觉少了点…

探索Python的魔法工具箱:functools

文章目录 探索Python的魔法工具箱&#xff1a;functools背景库介绍安装简单库函数使用方法lru_cachepartialreducecmp_to_keytotal_ordering 场景应用缓存数据库查询结果固定函数参数计算序列的累积和自动补全比较方法将比较函数转换为key函数 常见Bug及解决方案Bug 1: lru_cac…

leetcode 3266 K次乘运算后的最终数组II 题解

题目大意 原题面 给你一个数组 nums&#xff0c;然后进行 k 轮游戏&#xff0c;每轮游戏都会选择数组当中最小的元素然后乘上一个数 multiplier&#xff08;题目给出&#xff09;&#xff0c;问你 k 轮游戏结束之后&#xff0c;这个数组长什么样子&#xff0c;所有的元素要对 …

事务管理与锁机制

title: 事务管理与锁机制 date: 2024/12/14 updated: 2024/12/14 author: cmdragon excerpt: 在数据库系统中,事务管理至关重要,它确保多个数据库操作能够作为一个单一的逻辑单元来执行,从而维护数据的一致性和完整性。一个良好的事务管理系统能够解决并发操作带来的问题…

各种消息中间件介绍

消息中间件是一种在分布式系统中实现消息传递的软件架构&#xff0c;它允许不同的应用程序或系统组件之间异步地交换信息。 1. Apache Kafka Kafka是一个分布式流处理平台&#xff0c;能够处理高吞吐量的数据。它主要用于构建实时数据管道和流应用程序。 • Broker&#xff1a;…

mall-admin-web开源项目搭建教程(图文)

本章教程,介绍如何在本地部署运行mall-admin-web这个开源项目。 开源地址:https://gitee.com/macrozheng/mall-admin-web mall-admin-web是一个电商后台管理系统的前端项目,基于Vue+Element实现。主要包括商品管理、订单管理、会员管理、促销管理、运营管理、内容管理、统计…

使用FastGPT制做一个AI网站日志分析器

越来越的多网站面临每天上千次的扫描和各类攻击&#xff0c;及时发现攻击IP&#xff0c;并有效的屏蔽不良访问成为网站安全的重要保障&#xff0c;这里我们使用AI来完成对网站日志的日常分析。 我们来使用FastGPT来制做一个AI网站日志析器&#xff0c;下面就开始&#xff1a; …

npm : 无法加载文件 D:\nodejs\npm.ps1

问题描述 npm run serve 启动一个Vue项目&#xff0c;报错如下&#xff1a; npm : 无法加载文件 D:\nodejs\npm.ps1&#xff0c;因为在此系统上禁止运行脚本。有关详细信息&#xff0c;请参阅 https:/go.microsoft.com/fwlink/? LinkID135170 中的 about_Execution_Policies。…

UE4_贴花_贴花基础知识一

贴花可以将材料和各种材料元素投影到表面上。您可以使用它们来添加独特的效果。贴花 是一种可以投射到网格体&#xff08;包括静态网格体和骨骼网格体&#xff09;上的材质。无论这些网格体的移动性&#xff08;Mobility&#xff09;是静态&#xff08;Static&#xff09;还是可…

ShardingSphereProxy:快速入门

使用 Docker 运行 ShardingSphere 在基于 Docker 安装 ShardingSphere 时&#xff0c;按照官方文档《使用 Docker :: ShardingSphere》所提供的步骤操作即可。 在运行ShardingSphereProxy之前&#xff0c;我们需要基于我们的测试场景修改配置文件&#xff0c;我测试场景中主要…

Unity 获取鼠标点击位置物体贴图颜色

实现 Ray ray Camera.main.ScreenPointToRay(Input.mousePosition); if (Physics.Raycast(ray, out RaycastHit hit)) {textureCoord hit.textureCoord;textureCoord.x * textureMat.width;textureCoord.y * textureMat.height;textureColor textureMat.GetPixel(Mathf.Flo…

Python高性能web框架-FastApi教程:(3)路径操作装饰器方法的参数

路径操作装饰器方法的参数 1. 定义带有参数的POST请求路由 app.post(/items,tags[这是items测试接口],summary这是items测试的summary,description这是items测试的description,response_description这是items测试的response_description) def test():return {items: items数据…

基于SpringBoot的嗨玩旅游网站:一站式旅游信息服务平台的设计与实现

摘要 在旅游需求日益增长的今天&#xff0c;一个全面、便捷的旅游信息服务平台显得尤为重要。嗨玩旅游网站正是为了满足这一需求而设计的在线平台&#xff0c;它提供了包括景点信息、旅游线路、商品信息、社区信息和活动推广等在内的丰富旅游目的地信息&#xff0c;旨在帮助用…

【K8S系列】Kubernetes 资源对象的 YAML 文件示例及其详细介绍

在 Kubernetes 中&#xff0c;YAML 文件用于定义各种资源对象的配置&#xff0c;包括 Pods、Deployments、Services 等。以下是一些常见 Kubernetes 资源对象的 YAML 文件示例及其详细介绍。 一、Pod Pod 是 Kubernetes 中最基本的部署单位&#xff0c;通常包含一个或多个容器…

MVP模式的理解和实践

MVP&#xff08;Model-View-Presenter&#xff09;模式是一种用于组织代码的架构模式&#xff0c;主要用于用户界面的开发。它通过将应用程序的三个主要组件分开&#xff0c;提高了应用的可维护性和可测试性。本文将详细介绍MVP模式的理解和实践&#xff0c;并通过Java语言提供…

微信小程序中 crypto-js 加解密全攻略

一、引言 在微信小程序开发中&#xff0c;数据的安全至关重要。加解密技术在保护用户数据和应用程序的安全性方面起着关键作用。小程序在与服务器进行数据交互时&#xff0c;面临着数据泄露、篡改等安全风险。为了确保用户信息的安全&#xff0c;选择合适的加解密算法变得尤为…

Mac mini m4本地跑大模型(ollama + llama + ComfyUI + Stable Diffusion | flux)

change log 2024-12-11 10:28&#xff08;推荐重新观看&#xff09; 针对绘画大模型的使用做进一步的详细操作&#xff08;flux1dev&#xff09; 见篇节&#xff08;绘画大模型&#xff09; 2024-12-10 更新了基础的chat大模型和绘画大模型的基础环境搭建。 安装chat大模型&am…

jenkins harbor安装

Harbor是一个企业级Docker镜像仓库‌。 文章目录 1. 什么是Docker私有仓库2. Docker有哪些私有仓库3. Harbor简介4. Harbor安装 1. 什么是Docker私有仓库 Docker私有仓库是用于存储和管理Docker镜像的私有存储库。Docker默认会有一个公共的仓库Docker Hub&#xff0c;而与Dock…

Flutter 内嵌 unity3d for android

前言&#xff1a; 最近刚整完 unity3d hybridCLR 更新代码和资源&#xff0c;我们 趁热打铁 将 Unity3D 嵌入 Flutter 应用中。实现在 Flutter 使用 Unity3D, 可以做 小游戏 大游戏&#xff1b; 之前都是 内嵌 Webview 来实现的。虽然 CocosCreator 做出来的效果也不错&#xf…

移远EC200A-CN的OPENCPU使用GO开发嵌入式程序TBOX

演示地址&#xff1a; http://134.175.123.194:8811 admin admin 演示视频&#xff1a; https://www.bilibili.com/video/BV196q2YQEDP 主要功能 WatchDog 1. 守护进程 2. OTA远程升级 TBOX 1. 数据采集、数据可视化、数据上报&#xff08;内置Modbus TCP/RTU/ASCII,GPS协…