牛客NC93 设计LRU缓存结构【hard 链表,Map Java】
题目


题目链接:
https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84
思路
双向链表+map最新的数据放头结点,尾节点放最老的数据,没次移除尾巴节点本地考察链表的新增,删除,移动节点
参考答案Java
import java.util.*;public class Solution {Map<Integer, Node> cache = new HashMap<>();Node start, end;int cap = 0;public Solution(int capacity) {// write code herecap = capacity;}public int get(int key) {//key对应节点移动到头部,成为头节点if (!cache.containsKey(key)) return -1;Node cur = cache.get(key);int v = cur.data;Node next = cur.next;Node prev = cur.prev;if (next != null && prev != null) { //cur 要变成头结点next.prev = prev;prev.next = next;if (next.next == null) { //这里似乎可以不要end = next;}cur.next = start;start.prev = cur;start = cur;} else if (next != null) { //说明cur是头结点,不管了} else if (prev != null) { //自己是尾结点prev.next = null; //自己的prev要成为尾巴,prev.next设置为nullcur.next = start;start.prev = cur;start = cur;end = prev; //尾巴修改为自己的前一个节点}return v;}public void set(int key, int value) {if (cache.containsKey(key)) {cache.get(key).data = value;cache.put(key, cache.get(key));get(key); //使用一次,移动到头部} else {Node node = new Node(key, value);if (cap == 1) { //容量为1时特殊处理start = end = node;cache.clear();cache.put(key, node);return;}int size = cache.size();if (start == null) {start = node;end = node;cache.put(key, node);} else if (size < cap) { //不需要移除尾节点,直接修改头部node.next = start;start.prev = node;start = node;cache.put(key, node);} else {
// System.out.println();
// System.out.println(key+" == "+value);
// System.out.println();Node last = end;Node lastprev = last.prev;end = lastprev; //设置新的尾节点cache.remove(last.key);end.next = null;last = null;node.next = start;start.prev = node;start = node; //设置新的头结点cache.put(key, node);}//show(start);}}static class Node {int key;int data;Node prev;Node next;public Node(int k, int d) {key = k;data = d;}}public void show(Node root) { //帮助打印的,本答案可以不需要System.out.println("");Node t = root;Set<Integer> s = new HashSet<>();while (t != null) {System.out.print(t.key + "=>" + t.data + " ");t = t.next;//if(s.contains(t.data)) break;}System.out.println("");}}/*** Your Solution object will be instantiated and called as such:* Solution solution = new Solution(capacity);* int output = solution.get(key);* solution.set(key,value);*/
本答案在lintcode 上相同题目没有通过全部测试用例
https://www.lintcode.com/problem/134/
后期找到原因后再修改本答案
相关文章:
牛客NC93 设计LRU缓存结构【hard 链表,Map Java】
题目 题目链接: https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84 思路 双向链表map最新的数据放头结点,尾节点放最老的数据,没次移除尾巴节点本地考察链表的新增,删除,移动节点参考答案Java im…...
机器学习和深度学习 -- 李宏毅(笔记与个人理解1-6)
机器学习和深度学习教程 – 李宏毅(笔记与个人理解) day1 课程内容 什么是机器学习 找函数关键技术(深度学习) 函数 – 类神经网络来表示 ;输入输出可以是 向量或者矩阵等如何找到函数: supervised Lear…...
低功耗全极霍尔开关芯片 D02,磁性开关点精确,对工艺和温度变化不敏感
1、概述 D02 是一款低功耗全极霍尔开关,用于检测施加的磁通量密度,并提供一个数字输出,该输出指示所感测磁通量幅度的当前状态。这些应用的一个例子是翻盖手机中的 ON/OFF 开关。微功耗设计特别适合电池供电系统,如手机或笔记本电…...
初识--数据结构
什么是数据结构?我们为什么要学习数据结构呢....一系列的问题就促使我们不得不了解数据结构。我们不禁要问了,学习C语言不就够了吗?为什么还要学习数据结构呢?这是因为:数据结构能够解决C语言解决不了的问题࿰…...
人工智能前沿成科技竞争新高地
以下文章来源:经济参考报 近日,首届中国具身智能大会(CEAI 2024)在上海举行。作为人工智能领域的前沿热点,具身智能正逐步走进现实,成为当前全球科技竞争的新高地、未来产业的新赛道、经济发展的新引擎。 “…...
【算法刷题day23】Leetcode:669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树
文章目录 Leetcode 669. 修剪二叉搜索树解题思路代码总结 Leetcode 108. 将有序数组转换为二叉搜索树解题思路代码总结 Leetcode 538. 把二叉搜索树转换为累加树解题思路代码总结 草稿图网站 java的Deque Leetcode 669. 修剪二叉搜索树 题目:669. 修剪二叉搜索树 解…...
设计一个会议管理系统100问?
会议管理系统的基本功能有哪些?如何确保会议管理系统的安全性?会议管理系统可以支持多少种不同类型的会议?是否有权限管理功能?是否支持会议室预订功能?会议管理系统可以导入外部参与者信息吗?是否支持多种…...
一文搞懂BI、ERP、MES、SCM、PLM、CRM、WMS、APS、SCADA、QMS
在企业信息化数字化过程中我们经常遇到很多系统,比如:MES、ERP、SCM、WMS、APS、SCADA、PLM、QMS、CRM、EAM、BI,这些都是什么系统?有什么功能和作用?它们之间的关系是怎样的? 今天就一文简单分享。 术语 …...
全量知识系统 程序详细设计 之 先验逻辑-实现:从“平凡”回到“平凡” (QA 百度搜索)
Q1. 思考:数学中的平凡,和程序中的平凡(比如POJO)、语言中的平凡(比如纯文本),数据中的平凡(比如 Number)。因为我设计中的全知系统将设计的三个方面刻画为语言设计、程序…...
注解(Annotation) --java学习笔记
注解 就是Java代码里的特殊标记,比如:Override、Test等,作用是:让其他程序根据注解信息来决定怎么执行该程序注意:注解可以用在类上、构造器上、方法上、成员变量上、参数上、等位置处 自定义注解 就是自己定义注解 自定义注解到底该怎么写:…...
uniapp 小程序获取WiFi列表
<template><view ><button click"getWifiList">获取WiFi列表</button><scroll-view:scroll-top"scrollTop"scroll-yclass"content-pop"><viewclass"itemInfo"v-for"(item, index) in wifiList&…...
数据可视化-ECharts Html项目实战(11)
在之前的文章中,我们学习了如何在ECharts中特殊图表的双y图以及自定义形状词云图。想了解的朋友可以查看这篇文章。同时,希望我的文章能帮助到你,如果觉得我的文章写的不错,请留下你宝贵的点赞,谢谢。 数据可视化-ECh…...
【MySQL数据库 | 第二十四篇】Limit语句的性能问题和调优策略
前言: MySQL作为最流行的关系型数据库管理系统之一,被广泛应用于各种规模和类型的应用程序中。其强大的功能和灵活的查询语言使得开发人员能够高效地执行各种数据操作和分析。 然而,在处理大量数据或复杂查询时,一些开发人员可能…...
【数据结构】两两交换链表 复制带随机指针的链表
问题描述1 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 求解 使用一个栈S来存储相邻两个节点即可 /*** Definition for…...
网络安全流量平台_优缺点分析
FlowShadow(流影),Ntm(派网),Elastiflow。 Arkimesuricata,QNSMsuricata,Malcolm套件。 Malcolm套件优点:支持文件还原反病毒引擎(clamav/yara)…...
【c语言】自定义类型:结构体详解
目录 自定义类型:结构体 结构体类型的声明 结构体变量的创建和初始化 结构的特殊声明 结构的自引用 结构体内存对齐 对其规则 为什么存在内存对齐? 修改默认对⻬数 结构体传参 结构体实现位段 位段的内存分配 位段的跨平台问题 位段的应用…...
利用AbortController,取消正在发送的请求
参考文章:https://blog.csdn.net/qq_45560350/article/details/130588101 解决问题:再图层中点击仓库的时候,点击后又取消掉,我们希望这个请求可以被取消掉,我们口可以利用AbortController控制器对象 实操:…...
dockerhub右键快速搜索脚本
Chrome 浏览器扩展的后台脚本,用于创建右键菜单项,并根据用户的操作在新的标签页中打开 Docker Hub 网站或者进行搜索。 // 创建右键菜单项,用于打开 Docker Hub 网站 chrome.contextMenus.create({id: search-home, // 菜单项的唯一标识符t…...
类似微信的以文搜图功能实现
通过PaddleOCR识别图片中的文字,将识别结果报存到es中,利用es查询语句返回结果图片。 技术逻辑 PaddleOCR部署、es部署创建mapping将PaddleOCR识别结果保存至es通过查询,返回结果 前期准备 PaddleOCR、es部署请参考https://blog.csdn.net…...
Android 13.0 Launcher3定制化之最近任务的全部清除由左边移到下边显示
1.概述 在最近13.0的系统rom产品开发中,在Launcher3的定制化开发中,在最近任务列表中,发现点击recents最近任务键后 显示的全部清除按键在左边 由于是横屏的产品显示在左边不太合理 所以要求显示在下边比较合理,所以要从Launcher3的显示流程来解决这个问题 2. 最近任务全…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
STL 2迭代器
文章目录 1.迭代器2.输入迭代器3.输出迭代器1.插入迭代器 4.前向迭代器5.双向迭代器6.随机访问迭代器7.不同容器返回的迭代器类型1.输入 / 输出迭代器2.前向迭代器3.双向迭代器4.随机访问迭代器5.特殊迭代器适配器6.为什么 unordered_set 只提供前向迭代器? 1.迭代器…...
