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

java算法题每日多道六

138. 随机链表的复制

题目

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点

例如,如果原链表中有 XY 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 xy ,同样有 x.random --> y

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0n-1);如果不指向任何节点,则为 null

你的代码 接受原链表的头节点 head 作为传入参数。

答案

class Solution {Map<Node,Node> map = new HashMap();public Node copyRandomList(Node head) {if(head==null){return null;}if(!map.containsKey(head)){Node newHead = new Node(head.val);map.put(head,newHead);newHead.next = copyRandomList(head.next);newHead.random = copyRandomList(head.random);}return map.get(head);}
}








92. 反转链表 II

题目

给你单链表的头指针 head 和两个整数 leftright ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

示例 2:

输入:head = [5], left = 1, right = 1
输出:[5]

答案

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy = new ListNode(0,head);ListNode pre = dummy;ListNode curr = null;for(int i=0;i<left-1;i++){pre = pre.next;}curr = pre.next;ListNode post = null;for(int i=left;i<right;i++){post = curr.next;curr.next = post.next;post.next = pre.next;pre.next = post;}return dummy.next;}
}








19. 删除链表的倒数第 N 个结点

题目

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

答案

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0,head);ListNode fast = dummy;ListNode slow = dummy;for(int i=0;i<=n;i++){fast = fast.next;}while(fast!=null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}








82. 删除排序链表中的重复元素 II

题目

给定一个已排序的链表的头 head删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表

输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
输入:head = [1,1,1,2,3]
输出:[2,3]

答案

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(0,head);ListNode pre = dummy;ListNode curr = head;while(curr!=null && curr.next!=null){if(curr.val==curr.next.val){while(curr.next!=null && curr.val==curr.next.val){curr = curr.next;}pre.next = curr.next;curr = curr.next;}else{curr = curr.next;pre = pre.next;}}return dummy.next;}
}








61. 旋转链表

题目

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]
输入:head = [0,1,2], k = 4
输出:[2,0,1]

答案

class Solution {public ListNode rotateRight(ListNode head, int k) {if(head==null || k==0 || head.next==null){return head;}ListNode curr = head;int num = 1;while(curr.next!=null){curr = curr.next;num++;}int temp = num - k%num;if(temp==num){return head;}curr.next = head; while(temp-->0){curr = curr.next;}ListNode res = curr.next;curr.next = null;return res;}
}








86. 分隔链表

题目

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]

示例 2:

输入:head = [2,1], x = 2
输出:[1,2]

答案

class Solution {public ListNode partition(ListNode head, int x) {ListNode small = new ListNode(0);ListNode smallHead = small;ListNode large = new ListNode(0);ListNode largeHead = large;while(head!=null){if(head.val<x){small.next = head;small = small.next;head = head.next;}else{large.next = head;large = large.next;head = head.next;}}small.next = largeHead.next;large.next = null;return smallHead.next;}
}








146. LRU 缓存

题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

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

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

答案

class LRUCache extends LinkedHashMap<Integer,Integer>{private int capacity;public LRUCache(int capacity) {super(capacity,0.75F,true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key,-1);}public void put(int key, int value) {super.put(key,value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){return super.size() > capacity;}}

相关文章:

java算法题每日多道六

138. 随机链表的复制 题目 给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成&#xff0c;其中每个新节点的值都设为其对…...

C# 特性(Attribute)

C# 特性&#xff08;Attribute&#xff09; 文章目录 C# 特性&#xff08;Attribute&#xff09;Obsolete语法示例代码 创建自定义特性&#xff08;Attribute&#xff09; Obsolete 这个预定义特性标记了不应被使用的程序实体。它可以让您通知编译器丢弃某个特定的目标元素。例…...

Redis 教程系列之Redis 配置(三)

Redis 配置 Redis 的配置文件位于 Redis 安装目录下,文件名为 redis.conf(Windows 名为 redis.windows.conf)。 你可以通过 CONFIG 命令查看或设置配置项。 语法 Redis CONFIG 命令格式如下: redis 127.0.0.1:6379> CONFIG GET CONFIG_SETTING_NAME 实例 redis 127.0…...

Java实验03

Code1 package q3;public class Method01{public static void main(String[] args) {class Student{String name;String StuID;public Student(String name,String StuID){this.namename;this.StuIDStuID;}public void speak(String name, String stuID) {//输出学号与姓名Sys…...

安卓studio连接手机之后,一两秒之后就自动断开了。问题解决。

太坑了&#xff0c;安卓studio链接手机之后。几秒之后就断开了。我以为是adb的问题&#xff0c;就重新安装了一下adb。并且在环境变量中配置了Path的路径。然而并没有什么用啊。 经过排查原来是数据心虚了。线的接触不良。导致你刚接通的瞬间有相对较强的电流是因为有瞬间高电压…...

数字科技优化金融供给,内外协同激活新质生产力

来源 | 镭射财经&#xff08;leishecaijing&#xff09; 新一轮产业变革悄然发生&#xff0c;决定产业高度和竞争格局的底层生产力&#xff0c;也正在经历一场从量变到质变的跃迁。新质生产力则是这场跃迁后的最新呈现。 站在新质生产力爆发的时代拐点&#xff0c;金融业达成…...

「Linux系列」Shell 输入/输出重定向

文章目录 一、Shell 输入重定向二、Shell 输出重定向标准输出重定向&#xff1a;标准错误输出重定向&#xff1a;同时重定向标准输出和错误输出&#xff1a;禁用输出&#xff1a; 三、Shell 重定向命令输出重定向&#xff1a;错误输出重定向&#xff1a;标准输出和错误输出同时…...

java实现word转pdf

引入依赖包 <dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId><version>2.2.5.RELEASE</version></dependency><dependency><groupId…...

[flask] flask的基本介绍、flask快速搭建项目并运行

笔记 Flask Flask 本身相当于一个内核&#xff0c;其他几乎所有的功能都要用到扩展&#xff08;邮件扩展Flask-Mail&#xff0c;用户认证Flask-Login&#xff0c;数据库Flask-SQLAlchemy&#xff09;&#xff0c;都需要用第三方的扩展来实现。比如可以用 Flask 扩展加入ORM、…...

设计编程网站集:生活部分:饮食+农业,植物(暂记)

这里写目录标题 植物相关综合教程**大型植物&#xff1a;****高大乔木&#xff08;Trees&#xff09;&#xff1a;** 具有坚硬的木质茎&#xff0c;通常高度超过6米。例如&#xff0c;橡树、松树、榉树等。松树梧桐 **灌木&#xff08;Shrubs&#xff09;&#xff1a;** 比乔木…...

搜索二维矩阵

题目链接 搜索二维矩阵 题目描述 注意点 每行中的整数从左到右按非严格递增顺序排列每行的第一个整数大于前一行的最后一个整数1 < matrix.length, matrix[0].length < 100 解答思路 先二分查找找到target所处的行&#xff0c;找到行后再二分查找找到target所处的列…...

【LeetCode周赛】第 390 场周赛

目录 3090. 每个字符最多出现两次的最长子字符串 简单3091. 执行操作使数据元素之和大于等于 K 中等3092. 最高频率的 ID 中等3093. 最长公共后缀查询 困难 3090. 每个字符最多出现两次的最长子字符串 简单 3090. 每个字符最多出现两次的最长子字符串 分析&#xff1a; 数据量…...

leetcode 343.整数拆分

思路&#xff1a;记忆化搜索或者动态规划 我们首先捋一下思路&#xff0c;而且分析最优解这一类问题&#xff0c;我们需要几个步骤&#xff1a; 1.看问题的描述&#xff0c;找出问题问的最优问题是什么&#xff1b; 2.然后我们就模拟一下这个问题进行到最后一步是什么样子&a…...

部署Zabbix Agents添加使能监测服务器_Linux平台_Yum源/Archive多模式

Linux平台 一、从yum源脚本安装部署Zabbix-Agent,添加Linux Servers/PC 概述 Zabbix 主要有以下几个组件组成: Zabbix Server:Zabbix 服务端,Zabbix的核心组件,它负责接收监控数据并触发告警,还负责将监控数据持久化到数据库中。 Zabbix Agent:Zabbix客户端,部署在被监…...

吴恩达2022机器学习专项课程(一) 第一周课程实验:模型表示(Lab_03)

目标 学习如何使用一个变量实现线性回归模型。 导入需要的库 存储特征x和目标变量y 这是真实的训练集&#xff0c;[1.0,2.0]是房子的大小&#xff0c;[300,500]是房子的价格。 使用数组存储训练集的数据&#xff1a; x_train&#xff1a;存储的是所有特征&#xff0c;[1.…...

流畅的 Python 第二版(GPT 重译)(十)

第十八章&#xff1a;with、match 和 else 块 上下文管理器可能几乎与子例程本身一样重要。我们只是初步了解了它们。[…] Basic 有一个 with 语句&#xff0c;在许多语言中都有 with 语句。但它们的功能不同&#xff0c;它们都只是做一些非常浅显的事情&#xff0c;它们可以避…...

【自然语言处理七-经典论文-attention is all you need】

然语言处理七-经典论文-attention is all you need 摘要原文译文小结 1&#xff1a;引言原文译文小结 2&#xff1a;背景原文译文小结 3&#xff1a;模型架构原文译文小结 3.1 编码器和解码器原文译文小结 3.2 注意力原文译文小结3.2.1 缩放点积注意力原文总结 3.2.2 多头注意力…...

【嵌入式】STM32和I2C通信

一、简介 I2C(Inter IC Bus)是有飞利浦公司开发的一种通用数据总线&#xff0c;主要通过两个通信线SCL和SDA进行通信&#xff0c;其中SCL(Serial Clock)是时钟线&#xff0c;用于收发双方同步数据&#xff0c;SDA(Serial Data)是数据线&#xff0c;用于传输数据。是一种同步半…...

如何使用Harmony OS控制外设——输入输出?

相关知识点 Hi3861开发板第一个示例程序演示 熟悉使用DevEco Device Tool插件进行程序烧录 熟悉串口调试工具sscom的使用 官方文档中控制核心板上LED的led_example.c讲解及演示 源码路径&#xff1a;applications/sample/wifi-iot/app/iothardware/led_example.cHarmony OS …...

1.1-数组-704. 二分查找★

704. 二分查找 ★ 力扣题目链接&#xff0c;给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;搜索 nums 中的 target&#xff0c;如果存在返回下标&#xff0c;否则返回 -1。n 将在 [1, 10000]之间。 可以假设 nums 中的所…...

@electron/asar 源码解读:Filesystem类的设计与实现

electron/asar 源码解读&#xff1a;Filesystem类的设计与实现 【免费下载链接】asar Simple extensive tar-like archive format with indexing 项目地址: https://gitcode.com/gh_mirrors/as/asar 在Electron应用开发中&#xff0c;文件打包和管理是至关重要的环节。作…...

DeepSeek LintCode 3706 · 满足条件的数对的数量 public long countValidPairs(int[] nums1, int[] nums2, int dif

这个问题是 LintCode 3706 “满足条件的数对的数量”&#xff0c;要求统计满足 nums1[i] - nums1[j] < nums2[i] - nums2[j] diff&#xff08;其中 i < j&#xff09;的数对 (i, j) 的数量。 问题理解 给定两个数组 nums1 和 nums2&#xff0c;以及一个整数 diff&#…...

基于TuGraph的医疗知识图谱构建与智能问答实践

1. 医疗知识图谱构建全流程解析 医疗知识图谱作为医疗信息化的重要基础设施&#xff0c;正在深刻改变着医疗数据的组织方式和应用模式。不同于传统的关系型数据库&#xff0c;图数据库能够更直观地展现疾病、症状、药物等实体间的复杂关系。我们以TuGraph图数据库为例&#xff…...

如何在不同的机器上运行多个OpenClaw实例?

想让不同机器上的 OpenClaw 一起协作&#xff0c;其实就是搭建一个跨机器的 “小龙虾通信网络”。实现方式分两种&#xff1a;简单直连&#xff08;适合测试 / 小集群&#xff09;和远程网关&#xff08;适合生产 / 稳定协作&#xff09;。下面给你一套直接能跑的完整方案。一、…...

helm部署skywalking链路追踪 java

添加helm仓库 skywalking取别名 sw 名称可以任意写helm repo add sw https://apache.jfrog.io/artifactory/skywalking-helm helm repo list这里 sw 要与上面的 sw 名称 一样 从 Helm 仓库下载 SkyWalking 的 Chart 包&#xff0c;–untar 并自动解压到当前目录helm pull sw/s…...

seo推广外包需要多少投入_seo推广外包如何避免被算法惩罚

SEO推广外包需要多少投入_SEO推广外包如何避免被算法惩罚 在当今数字化经济时代&#xff0c;SEO&#xff08;搜索引擎优化&#xff09;推广已经成为企业提升网站流量和品牌知名度的重要手段。随着搜索引擎算法的不断更新&#xff0c;企业在进行SEO推广外包时&#xff0c;不仅需…...

3分钟掌握绝地求生压枪黑科技:罗技鼠标宏终极指南

3分钟掌握绝地求生压枪黑科技&#xff1a;罗技鼠标宏终极指南 【免费下载链接】logitech-pubg PUBG no recoil script for Logitech gaming mouse / 绝地求生 罗技 鼠标宏 项目地址: https://gitcode.com/gh_mirrors/lo/logitech-pubg 还在为《绝地求生》中AKM的后坐力而…...

CST可调谐太赫兹超材料吸收器仿真教学,石墨烯,二氧化钒,锑化铟等材料设置 包括建模过程,后处理

CST可调谐太赫兹超材料吸收器仿真教学&#xff0c;石墨烯&#xff0c;二氧化钒&#xff0c;锑化铟等材料设置 包括建模过程&#xff0c;后处理&#xff0c;吸收光谱图教学等 包括宽带吸收器、窄带&#xff0c;以及宽窄带吸收器设计"打开CST微波工作室&#xff0c;先别急着…...

COMSOL电磁超声仿真技术:基于5.6版本模型,精确检测L形铝板裂纹的电磁超声测量方法

COMSOL电磁超声仿真: Crack detection in L-shaped aluminum plate via electromagnetic ultrasonic measurements 版本为5.6&#xff0c;低于5.6的版本打不开此模型电磁超声检测&#xff08;EMAT&#xff09;在工业无损检测领域一直是个热门方向&#xff0c;最近在COMSOL 5.6上…...

一个简洁易用的 Delphi JSON 封装库,基于 System.JSON`单元封装,提供更直观的 API

pagehelper整合 引入依赖com.github.pagehelperpagehelper-spring-boot-starter2.1.0compile编写代码 GetMapping("/list/{pageNo}") public PageInfo findAll(PathVariable int pageNo) {// 设置当前页码和每页显示的条数PageHelper.startPage(pageNo, 10);// 查询数…...