牛客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. 最近任务全…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...

2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...