当前位置: 首页 > news >正文

牛客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】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84 思路 双向链表map最新的数据放头结点&#xff0c;尾节点放最老的数据&#xff0c;没次移除尾巴节点本地考察链表的新增&#xff0c;删除&#xff0c;移动节点参考答案Java im…...

机器学习和深度学习 -- 李宏毅(笔记与个人理解1-6)

机器学习和深度学习教程 – 李宏毅&#xff08;笔记与个人理解&#xff09; day1 课程内容 什么是机器学习 找函数关键技术&#xff08;深度学习&#xff09; 函数 – 类神经网络来表示 &#xff1b;输入输出可以是 向量或者矩阵等如何找到函数&#xff1a; supervised Lear…...

低功耗全极霍尔开关芯片 D02,磁性开关点精确,对工艺和温度变化不敏感

1、概述 D02 是一款低功耗全极霍尔开关&#xff0c;用于检测施加的磁通量密度&#xff0c;并提供一个数字输出&#xff0c;该输出指示所感测磁通量幅度的当前状态。这些应用的一个例子是翻盖手机中的 ON/OFF 开关。微功耗设计特别适合电池供电系统&#xff0c;如手机或笔记本电…...

初识--数据结构

什么是数据结构&#xff1f;我们为什么要学习数据结构呢....一系列的问题就促使我们不得不了解数据结构。我们不禁要问了&#xff0c;学习C语言不就够了吗&#xff1f;为什么还要学习数据结构呢&#xff1f;这是因为&#xff1a;数据结构能够解决C语言解决不了的问题&#xff0…...

人工智能前沿成科技竞争新高地

以下文章来源&#xff1a;经济参考报 近日&#xff0c;首届中国具身智能大会&#xff08;CEAI 2024&#xff09;在上海举行。作为人工智能领域的前沿热点&#xff0c;具身智能正逐步走进现实&#xff0c;成为当前全球科技竞争的新高地、未来产业的新赛道、经济发展的新引擎。 “…...

【算法刷题day23】Leetcode:669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树

文章目录 Leetcode 669. 修剪二叉搜索树解题思路代码总结 Leetcode 108. 将有序数组转换为二叉搜索树解题思路代码总结 Leetcode 538. 把二叉搜索树转换为累加树解题思路代码总结 草稿图网站 java的Deque Leetcode 669. 修剪二叉搜索树 题目&#xff1a;669. 修剪二叉搜索树 解…...

设计一个会议管理系统100问?

会议管理系统的基本功能有哪些&#xff1f;如何确保会议管理系统的安全性&#xff1f;会议管理系统可以支持多少种不同类型的会议&#xff1f;是否有权限管理功能&#xff1f;是否支持会议室预订功能&#xff1f;会议管理系统可以导入外部参与者信息吗&#xff1f;是否支持多种…...

一文搞懂BI、ERP、MES、SCM、PLM、CRM、WMS、APS、SCADA、QMS

在企业信息化数字化过程中我们经常遇到很多系统&#xff0c;比如&#xff1a;MES、ERP、SCM、WMS、APS、SCADA、PLM、QMS、CRM、EAM、BI&#xff0c;这些都是什么系统&#xff1f;有什么功能和作用&#xff1f;它们之间的关系是怎样的&#xff1f; 今天就一文简单分享。 术语 …...

全量知识系统 程序详细设计 之 先验逻辑-实现:从“平凡”回到“平凡” (QA 百度搜索)

Q1. 思考&#xff1a;数学中的平凡&#xff0c;和程序中的平凡&#xff08;比如POJO&#xff09;、语言中的平凡&#xff08;比如纯文本&#xff09;&#xff0c;数据中的平凡&#xff08;比如 Number&#xff09;。因为我设计中的全知系统将设计的三个方面刻画为语言设计、程序…...

注解(Annotation) --java学习笔记

注解 就是Java代码里的特殊标记&#xff0c;比如:Override、Test等&#xff0c;作用是:让其他程序根据注解信息来决定怎么执行该程序注意:注解可以用在类上、构造器上、方法上、成员变量上、参数上、等位置处 自定义注解 就是自己定义注解 自定义注解到底该怎么写&#xff1a…...

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)

在之前的文章中&#xff0c;我们学习了如何在ECharts中特殊图表的双y图以及自定义形状词云图。想了解的朋友可以查看这篇文章。同时&#xff0c;希望我的文章能帮助到你&#xff0c;如果觉得我的文章写的不错&#xff0c;请留下你宝贵的点赞&#xff0c;谢谢。 数据可视化-ECh…...

【MySQL数据库 | 第二十四篇】Limit语句的性能问题和调优策略

前言&#xff1a; MySQL作为最流行的关系型数据库管理系统之一&#xff0c;被广泛应用于各种规模和类型的应用程序中。其强大的功能和灵活的查询语言使得开发人员能够高效地执行各种数据操作和分析。 然而&#xff0c;在处理大量数据或复杂查询时&#xff0c;一些开发人员可能…...

【数据结构】两两交换链表 复制带随机指针的链表

问题描述1 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09;。 求解 使用一个栈S来存储相邻两个节点即可 /*** Definition for…...

网络安全流量平台_优缺点分析

FlowShadow&#xff08;流影&#xff09;&#xff0c;Ntm&#xff08;派网&#xff09;&#xff0c;Elastiflow。 Arkimesuricata&#xff0c;QNSMsuricata&#xff0c;Malcolm套件。 Malcolm套件优点&#xff1a;支持文件还原反病毒引擎&#xff08;clamav/yara&#xff09;…...

【c语言】自定义类型:结构体详解

目录 自定义类型&#xff1a;结构体 结构体类型的声明 结构体变量的创建和初始化 结构的特殊声明 结构的自引用 结构体内存对齐 对其规则 为什么存在内存对齐&#xff1f; 修改默认对⻬数 结构体传参 结构体实现位段 位段的内存分配 位段的跨平台问题 位段的应用…...

利用AbortController,取消正在发送的请求

参考文章&#xff1a;https://blog.csdn.net/qq_45560350/article/details/130588101 解决问题&#xff1a;再图层中点击仓库的时候&#xff0c;点击后又取消掉&#xff0c;我们希望这个请求可以被取消掉&#xff0c;我们口可以利用AbortController控制器对象 实操&#xff1a…...

dockerhub右键快速搜索脚本

Chrome 浏览器扩展的后台脚本&#xff0c;用于创建右键菜单项&#xff0c;并根据用户的操作在新的标签页中打开 Docker Hub 网站或者进行搜索。 // 创建右键菜单项&#xff0c;用于打开 Docker Hub 网站 chrome.contextMenus.create({id: search-home, // 菜单项的唯一标识符t…...

类似微信的以文搜图功能实现

通过PaddleOCR识别图片中的文字&#xff0c;将识别结果报存到es中&#xff0c;利用es查询语句返回结果图片。 技术逻辑 PaddleOCR部署、es部署创建mapping将PaddleOCR识别结果保存至es通过查询&#xff0c;返回结果 前期准备 PaddleOCR、es部署请参考https://blog.csdn.net…...

Android 13.0 Launcher3定制化之最近任务的全部清除由左边移到下边显示

1.概述 在最近13.0的系统rom产品开发中,在Launcher3的定制化开发中,在最近任务列表中,发现点击recents最近任务键后 显示的全部清除按键在左边 由于是横屏的产品显示在左边不太合理 所以要求显示在下边比较合理,所以要从Launcher3的显示流程来解决这个问题 2. 最近任务全…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...