java算法题每日多道六
138. 随机链表的复制
题目
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示Node.val的整数。random_index:随机指针指向的节点索引(范围从0到n-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 和两个整数 left 和 right ,其中 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,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 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 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对…...
C# 特性(Attribute)
C# 特性(Attribute) 文章目录 C# 特性(Attribute)Obsolete语法示例代码 创建自定义特性(Attribute) 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连接手机之后,一两秒之后就自动断开了。问题解决。
太坑了,安卓studio链接手机之后。几秒之后就断开了。我以为是adb的问题,就重新安装了一下adb。并且在环境变量中配置了Path的路径。然而并没有什么用啊。 经过排查原来是数据心虚了。线的接触不良。导致你刚接通的瞬间有相对较强的电流是因为有瞬间高电压…...
数字科技优化金融供给,内外协同激活新质生产力
来源 | 镭射财经(leishecaijing) 新一轮产业变革悄然发生,决定产业高度和竞争格局的底层生产力,也正在经历一场从量变到质变的跃迁。新质生产力则是这场跃迁后的最新呈现。 站在新质生产力爆发的时代拐点,金融业达成…...
「Linux系列」Shell 输入/输出重定向
文章目录 一、Shell 输入重定向二、Shell 输出重定向标准输出重定向:标准错误输出重定向:同时重定向标准输出和错误输出:禁用输出: 三、Shell 重定向命令输出重定向:错误输出重定向:标准输出和错误输出同时…...
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 本身相当于一个内核,其他几乎所有的功能都要用到扩展(邮件扩展Flask-Mail,用户认证Flask-Login,数据库Flask-SQLAlchemy),都需要用第三方的扩展来实现。比如可以用 Flask 扩展加入ORM、…...
设计编程网站集:生活部分:饮食+农业,植物(暂记)
这里写目录标题 植物相关综合教程**大型植物:****高大乔木(Trees):** 具有坚硬的木质茎,通常高度超过6米。例如,橡树、松树、榉树等。松树梧桐 **灌木(Shrubs):** 比乔木…...
搜索二维矩阵
题目链接 搜索二维矩阵 题目描述 注意点 每行中的整数从左到右按非严格递增顺序排列每行的第一个整数大于前一行的最后一个整数1 < matrix.length, matrix[0].length < 100 解答思路 先二分查找找到target所处的行,找到行后再二分查找找到target所处的列…...
【LeetCode周赛】第 390 场周赛
目录 3090. 每个字符最多出现两次的最长子字符串 简单3091. 执行操作使数据元素之和大于等于 K 中等3092. 最高频率的 ID 中等3093. 最长公共后缀查询 困难 3090. 每个字符最多出现两次的最长子字符串 简单 3090. 每个字符最多出现两次的最长子字符串 分析: 数据量…...
leetcode 343.整数拆分
思路:记忆化搜索或者动态规划 我们首先捋一下思路,而且分析最优解这一类问题,我们需要几个步骤: 1.看问题的描述,找出问题问的最优问题是什么; 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 这是真实的训练集,[1.0,2.0]是房子的大小,[300,500]是房子的价格。 使用数组存储训练集的数据: x_train:存储的是所有特征,[1.…...
流畅的 Python 第二版(GPT 重译)(十)
第十八章:with、match 和 else 块 上下文管理器可能几乎与子例程本身一样重要。我们只是初步了解了它们。[…] Basic 有一个 with 语句,在许多语言中都有 with 语句。但它们的功能不同,它们都只是做一些非常浅显的事情,它们可以避…...
【自然语言处理七-经典论文-attention is all you need】
然语言处理七-经典论文-attention is all you need 摘要原文译文小结 1:引言原文译文小结 2:背景原文译文小结 3:模型架构原文译文小结 3.1 编码器和解码器原文译文小结 3.2 注意力原文译文小结3.2.1 缩放点积注意力原文总结 3.2.2 多头注意力…...
【嵌入式】STM32和I2C通信
一、简介 I2C(Inter IC Bus)是有飞利浦公司开发的一种通用数据总线,主要通过两个通信线SCL和SDA进行通信,其中SCL(Serial Clock)是时钟线,用于收发双方同步数据,SDA(Serial Data)是数据线,用于传输数据。是一种同步半…...
如何使用Harmony OS控制外设——输入输出?
相关知识点 Hi3861开发板第一个示例程序演示 熟悉使用DevEco Device Tool插件进行程序烧录 熟悉串口调试工具sscom的使用 官方文档中控制核心板上LED的led_example.c讲解及演示 源码路径:applications/sample/wifi-iot/app/iothardware/led_example.cHarmony OS …...
1.1-数组-704. 二分查找★
704. 二分查找 ★ 力扣题目链接,给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,搜索 nums 中的 target,如果存在返回下标,否则返回 -1。n 将在 [1, 10000]之间。 可以假设 nums 中的所…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
