设计链表(不难,代码稍微多一点)
设计链表
在链表类中实现这些功能:
- get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
- addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
- addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
思路
这道题目,我觉得是链表部分最好的练习链表操作的一道题目,虽然不一定是考的频率最高的。为什么这么说?
- 删除元素
- 新增元素
- 查询元素
上述对链表的操作都已经涉及。
类中的属性
根据题目第4点要求,我们可以知道,这个自定义链表中一定有个 size
属性,记录当前链表的长度。(不然你怎么判断index?)
根据上一篇文章移除链表元素我们可以知道,这里需要一个虚拟头结点来处理删除操作。
各个方法的代码
分析一下 addAtHead()
和 addAtTail()
可以合并到 addAtIndex()
方法中
大概就是:
addAtHead(val)
== addAtIndex(0,val)
addAtTail(val)
== addAtIndex(size,val)
所以,我们真正需要写的方法只有 get(index)
、deleteAtIndex(index)
、 addAtIndex(index,val)
三个方法。我们先从难的开始
addAtIndex(index,val)
先不考虑头尾这两个特例。
正常插入
我们先想一下在正常结点中插入数据
- 找到需要插入的前驱节点(注意一定要是前驱节点)也就是上图中C.
- new 一个新节点
- newNode的next -> 前驱节点的next
- 前驱节点的next -> newNode
- size++
插入头(head)
我们这里使用的虚拟节点,采用上述方法可以直接插入
插入尾(tail)
仔细一想,好像也可以,没问题。
相关代码:
public void addAtIndex(int index,int val) {if (index > size) {return;} else if (index <= 0) {index = 0;}ListNode newLinedList = new ListNode(val);ListNode preNode = head;for (int i = 0; i < index; i++) {preNode = preNode.next;}//这一步很重要,顺序不能反。//一定是新节点先指向下一个,然后再断开前驱节点的nextnewLinedList.next = preNode.next;preNode.next = newLinedList;size++;}
话说回来,因为我们是用size+ 虚拟头节点,所以插入头、尾只是size的值不同,所以不会有什么特殊处理的地方。删除操作也是一样。
deleteAtIndex(index)
遍历到需要删除的节点的前驱节点(黑人问号脸?又是前驱节点?大家可以想一下,为什么不管是新增还是删除都需要前驱节点)
删除很简单 :伪代码: preNode.next = preNode.next.next
实际代码:
public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//删除节点dummyHead.next = dummyHead.next.next;size--;}
get(index)
get其实和删除差不多,但是唯一需要注意的是,我们是虚拟头结点,所以在遍历获取到的节点是前驱节点,返回的是 preNode.next.val
代码:
public int get(int index) {//这里需要带等号if (index < 0 || index >= size) {return -1;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//注意是虚拟头结点,所以需要返回next.valreturn dummyHead.next.val;}
代码
public class MyLinkedList {/*** 虚拟头结点*/ListNode head;int size;MyLinkedList() {size = 0;head = new ListNode(0);}public void addAtIndex(int index, int val) {if (index > size) {return;} else if (index <= 0) {index = 0;}ListNode newLinedList = new ListNode(val);ListNode preNode = head;for (int i = 0; i < index; i++) {preNode = preNode.next;}//这一步很重要,顺序不能反。//一定是新节点先指向下一个,然后再断开前驱节点的nextnewLinedList.next = preNode.next;preNode.next = newLinedList;size++;}public int get(int index) {//这里需要带等号if (index < 0 || index >= size) {return -1;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//注意是虚拟头结点,所以需要返回next.valreturn dummyHead.next.val;}public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}ListNode dummyHead = head;for (int i = 0; i < index; i++) {dummyHead = dummyHead.next;}//删除节点dummyHead.next = dummyHead.next.next;size--;}public void addAtHead(int val) {addAtIndex(0, val);}public void addAtTail(int val) {addAtIndex(size, val);}}
总结
- 利用虚拟节点处理 删除、更新操作。
- 注意get方法获取的返回的值应该是:
preNode.next.val
。 - 新增节点的时候,注意下代码顺序。
相关文章:
设计链表(不难,代码稍微多一点)
设计链表 在链表类中实现这些功能: get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。ad…...
[GXYCTF2019]禁止套娃
进来发现只有这句话,习惯性访问一下flag.php,发现不是404,那就证明flag就在这了,接下来要想办法拿到flag.php的源码。 这道题是.git文件泄露网页源码,githack拿到index.php源码 这里观察到多次判断,首先要…...
ubuntu下如何查看显卡及显卡驱动
ubuntu下如何查看显卡及显卡驱动 使用nvidia-smi 工具查看 查看显卡型号nvida-smi -L $ nvidia-smi -L GPU 0: NVIDIA GeForce RTX 3050 4GB Laptop GPU (UUID: GPU-4cf7b7cb-f103-bf56-2d59-304f8996e28c)当然直接使用nvida-smi 命令可以查看更多信息 $ nvidia-smi Mon Fe…...
【图论经典题目讲解】CF786B - Legacy 一道线段树优化建图的经典题目
C F 786 B − L e g a c y \mathrm{CF786B - Legacy} CF786B−Legacy D e s c r i p t i o n \mathrm{Description} Description 给定 1 1 1 张 n n n 个点的有向图,初始没有边,接下来有 q q q 次操作,形式如下: 1 u v w 表示…...
【AIGC】Stable Diffusion的采样器入门
在 Stable Diffusion 中,采样器(Sampler)是指用于生成图像的一种技术或方法,它决定了模型如何从潜在空间中抽样并生成图像。采样器在生成图像的过程中起着重要作用,影响着生成图像的多样性、质量和创造性。以下是对 St…...
【Python】通过conda安装Python的IDE
背景 系统:win11 软件:anaconda Navigator 问题现象:①使用Navigator安装jupyter notebook以及Spyder IDE 一直转圈。②然后进入anaconda prompt执行conda install jupyter notebook一直卡在Solving environment/-\。 类似问题: …...
基于HTML5实现动态烟花秀效果(含音效和文字)实战
目录 前言 一、烟花秀效果功能分解 1、功能分解 2、界面分解 二、HTML功能实现 1、html界面设计 2、背景音乐和燃放触发 3、燃放控制 4、对联展示 5、脚本引用即文本展示 三、脚本调用及实现 1、烟花燃放 2、燃放响应 3、烟花canvas创建 4、燃放声音控制 5、实际…...
「数据结构」栈和队列
栈 栈的基本概念 定义 栈是只允许在一端进行插入或删除操作的线性表栈顶:线性表允许进行插入删除的那一端栈底:固定的,不允许进行插入和删除的另一端空栈:不含任何元素特点:后进先出(LIFO) 基…...
【机器学习笔记】5 机器学习实践
数据集划分 子集划分 训练集(Training Set):帮助我们训练模型,简单的说就是通过训练集的数据让我们确定拟合曲线的参数。 验证集(Validation Set):也叫做开发集( Dev Set …...
C++ //练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。
C Primer(第5版) 练习 7.5 练习 7.5 在你的Person类中提供一些操作使其能够返回姓名和住址。这些函数是否应该是const的呢?解释原因。 环境:Linux Ubuntu(云服务器) 工具:vim 解释 姓名大概…...
python系统学习Day2
section3 python Foudamentals part one:data types and variables 数据类型:整数、浮点数、字符串、布尔值、空值 #整型,没有大小限制 >>>9 / 3 #3.0 >>>10 // 3 #3 地板除 >>>10 % 3 #1 取余#浮点型ÿ…...
学习笔记——ENM模拟
学习笔记——ENM模拟 文章目录 前言一、文献一1. 材料与方法1.1. 大致概念1.2. 生态模型的构建1.2.1. 数据来源:1.2.2. 数据处理:1.2.3. 模型参数优化: 1.3. 适生情况预测1.3.1. 预测模型构建1.3.2. 适生区划分 1.4. 模型的评估与验证 2. 结果…...
数值类型的运算方式总结
提纲1:常见的位运算使用场景 提纲2:整数类型运算时的类型溢出问题,产生原因以及解决办法 提纲3:浮点类型运算时的精度丢失问题,产生原因以及解决办法 数值类型(6种)分为: 整型&…...
【Redis快速入门】Redis三种集群搭建配置(主从集群、哨兵集群、分片集群)
个人名片: 🐼作者简介:一名大三在校生,喜欢AI编程🎋 🐻❄️个人主页🥇:落798. 🐼个人WeChat:hmmwx53 🕊️系列专栏:🖼️…...
[嵌入式系统-14]:常见实时嵌入式操作系统比较:RT-Thread、uC/OS-II和FreeRTOS、Linux
目录 一、实时嵌入式操作系统 1.1 概述 1.2 什么“实时” 1.3 什么是硬实时和软实时 1.4 什么是嵌入式 1.5 什么操作系统 二、常见重量级操作系统 三、常见轻量级嵌入式操作系统 3.1 概述 3.2 FreeRTOS 3.3 uC/OS-II 3.4 RT-Thread 3.5 RT-Thread、uC/OS-II、Free…...
基于AI Agent探讨:安全领域下的AI应用范式
先说观点:关于AI应用,通常都会聊准召。但在安全等模糊标准的场景下,事实上不存在准召的定义。因此,AI的目标应该是尽可能的“像人”。而想要评价有多“像人”,就先需要将人的工作数字化。而AI Agent是能够将数字化、自…...
Stable Diffusion 模型下载:ToonYou(平涂卡通)
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十...
机器学习:分类决策树(Python)
一、各种熵的计算 entropy_utils.py import numpy as np # 数值计算 import math # 标量数据的计算class EntropyUtils:"""决策树中各种熵的计算,包括信息熵、信息增益、信息增益率、基尼指数。统一要求:按照信息增益最大、信息增益率…...
红队打靶练习:HACK ME PLEASE: 1
信息收集 1、arp ┌──(root㉿ru)-[~/kali] └─# arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:69:c7:bf, IPv4: 192.168.61.128 Starting arp-scan 1.10.0 with 256 hosts (https://github.com/royhills/arp-scan) 192.168.61.2 00:50:56:f0:df:20 …...
《VulnHub》GoldenEye:1
title: 《VulnHub》GoldenEye:1 date: 2024-02-16 14:53:49 updated: 2024-02-16 15:08:49 categories: WriteUp:Cyber-Range excerpt: 主机发现、目标信息扫描、源码 js 文件泄露敏感信息、hydra 爆破邮件服务(pop3)、邮件泄露敏…...
html的表格标签
html的表格标签 table标签:表示整个表格tr:表示表格的一行td:表示一个单元格th:表示表头单元格.会居中加粗thead:表格的头部区域 (注意和th区分,范围是比th要大的).tbody:表格得到主体区域. table包含tr , tr包含td或者th. 表格标签有一些属性,可以用于设置大小边…...
蓝桥杯(Web大学组)2022省赛真题:展开你的扇子
思路: transform-origin: center bottom;使盒子旋转时,以底部的中心为坐标原点(题目已给出) 对每个盒子使用transform: rotate();实现旋转 笔记: 设置悬浮旋转时, #box div:hover #item6{ } 为什…...
复习基础知识1
局部变量 写程序时,程序员经常会用到局部变量 汇编中寄存器、栈,可写区段、堆,函数的局部变量该存在哪里呢? 注意:局部变量有易失性 一旦函数返回,则所有局部变量会失效。 考虑到这种特性,人们…...
java8-用流收集数据-6
本章内容口用co1lectors类创建和使用收集器 口将数据流归约为一个值 口汇总:归约的特殊情况 数据分组和分区口 口 开发自己的自定义收集器 我们在前一章中学到,流可以用类似于数据库的操作帮助你处理集合。你可以把Java8的流看作花哨又懒惰的数据集迭代器。它们…...
[前端开发] JavaScript基础知识 [上]
下篇:JavaScript基础知识 [下] JavaScript基础知识 [上] 引言语句、标识符和变量JavaScript引入注释与输出数据类型运算符条件语句与循环语句 引言 JavaScript是一种广泛应用于网页开发的脚本语言,具有重要的前端开发和部分后端开发的应用。通过JavaSc…...
初识Qt | 从安装到编写Hello World程序
文章目录 1.前端开发简单分类2.Qt的简单介绍3.Qt的安装和环境配置4.创建简单的Qt项目 1.前端开发简单分类 前端开发,这里是一个广义的概念,不单指网页开发,它的常见分类 网页开发:前端开发的主要领域,使用HTML、CSS …...
机器学习:过拟合和欠拟合的介绍与解决方法
过拟合和欠拟合的表现和解决方法。 其实除了欠拟合和过拟合,还有一种是适度拟合,适度拟合就是我们模型训练想要达到的状态,不过适度拟合这个词平时真的好少见。 过拟合 过拟合的表现 模型在训练集上的表现非常好,但是在测试集…...
变分自编码器(VAE)PyTorch Lightning 实现
✅作者简介:人工智能专业本科在读,喜欢计算机与编程,写博客记录自己的学习历程。 🍎个人主页:小嗷犬的个人主页 🍊个人网站:小嗷犬的技术小站 🥭个人信条:为天地立心&…...
设备驱动开发_1
可加载模块如何工作的 主要内容 描述可加载模块优势使用模块命令效率使用和定义模块密钥和模块工作1 描述可加载模块优势 开发周期优势: 静态模块在/boot下的vmlinuz中,需要配置、编译、重启。 开发周期长。 LKM 不需要重启。 开发周期优于静态模块。 2 使用模块命令效率…...
C语言位域(Bit Fields)知识点精要解析
在C语言中,位域(Bit Field)是一种独特的数据结构特性,它允许程序员在结构体(struct)中定义成员变量,并精确指定其占用的位数。通过使用位域,我们可以更高效地利用存储空间࿰…...
离散数学——图论(笔记及思维导图)
离散数学——图论(笔记及思维导图) 目录 大纲 内容 参考 大纲 内容 参考 笔记来自【电子科大】离散数学 王丽杰...
opencv图像像素的读写操作
void QuickDemo::pixel_visit_demo(Mat & image) {int w image.cols;//宽度int h image.rows;//高度int dims image.channels();//通道数 图像为灰度dims等于一 图像为彩色时dims等于三 for (int row 0; row < h; row) {for (int col 0; col < w; col) {if…...
Java学习第十四节之冒泡排序
冒泡排序 package array;import java.util.Arrays;//冒泡排序 //1.比较数组中,两个相邻的元素,如果第一个数比第二个数大,我们就交换他们的位置 //2.每一次比较,都会产生出一个最大,或者最小的数字 //3.下一轮则可以少…...
第1章 计算机网络体系结构-1.1计算机网络概述
1.1.1计算机网络概念 计算机网络是将一个分散的,具有独立功能的计算机系统通过通信设备与路线连接起来,由功能完善的软件实现资源共享和信息传递的系统。(计算机网络就是一些互连的,自治的计算机系统的集合) 1.1.2计算机网络的组成 从不同角…...
蓝桥杯:C++排序
排序 排序和排列是算法题目常见的基本算法。几乎每次蓝桥杯软件类大赛都有题目会用到排序或排列。常见的排序算法如下。 第(3)种排序算法不是基于比较的,而是对数值按位划分,按照以空间换取时间的思路来排序。看起来它们的复杂度更好,但实际…...
数据结构-堆
1.容器 容器用于容纳元素集合,并对元素集合进行管理和维护. 传统意义上的管理和维护就是:增,删,改,查. 我们分析每种类型容器时,主要分析其增,删,改ÿ…...
奔跑吧小恐龙(Java)
前言 Google浏览器内含了一个小彩蛋当没有网络连接时,浏览器会弹出一个小恐龙,当我们点击它时游戏就会开始进行,大家也可以玩一下试试,网址:恐龙快跑 - 霸王龙游戏. (ur1.fun) 今天我们也可以用Java来简单的实现一下这…...
Ubuntu 1804 And Above Coredump Settings
查看 coredump 是否开启 # 查询, 0 未开启, unlimited 开启 xiaoUbuntu:/var/core$ ulimit -c 0# 开启 xiaoUbuntu:/var/core$ ulimit -c unlimited查看 coredump 保存路径 默认情况下,Ubuntu 使用 apport 服务处理 coredump 文件ÿ…...
docker 2:安装
docker 2:安装 ubuntu 安装 docker sudo apt install docker.io 把当前用户放进 docker 用户组,避免每次运行 docker 命都要使用 sudo 或者 root 权限。 sudo usermod -aG docker $USERid $USER 看到用户已加入 docker 组 …...
LeetCode Python - 19.删除链表的倒数第N个结点
目录 题目答案运行结果 题目 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head [1,2,3,4,5], n 2 输出:[1,2,3,5] 示例 2: 输入:head [1], n 1 输出&a…...
Spring Boot 笔记 005 环境搭建
1.1 创建数据库和表(略) 2.1 创建Maven工程 2.2 补齐resource文件夹和application.yml文件 2.3 porn.xml中引入web,mybatis,mysql等依赖 2.3.1 引入springboot parent 2.3.2 删除junit 依赖--不能删,删了会报错 2.3.3 引入spring web依赖…...
【解决(几乎)任何机器学习问题】:超参数优化篇(超详细)
这篇文章相当长,您可以添加至收藏夹,以便在后续有空时候悠闲地阅读。 有了优秀的模型,就有了优化超参数以获得最佳得分模型的难题。那么,什么是超参数优化呢?假设您的机器学习项⽬有⼀个简单的流程。有⼀个数据集&…...
面试计算机网络框架八股文十问十答第七期
面试计算机网络框架八股文十问十答第七期 作者:程序员小白条,个人博客 相信看了本文后,对你的面试是有一定帮助的!关注专栏后就能收到持续更新! ⭐点赞⭐收藏⭐不迷路!⭐ 1)UDP协议为什么不可…...
Codeforces Round 926 (Div. 2)
A. Sasha and the Beautiful Array(模拟) 思路 最大值减去最小值 #include<iostream> #include<algorithm> using namespace std; const int N 110; int a[N];int main(){int t, n;cin>>t;while(t--){cin>>n;for(int i 0; i…...
构建智慧交通平台:架构设计与实现
随着城市交通的不断发展和智能化技术的迅速进步,智慧交通平台作为提升城市交通管理效率和水平的重要手段备受关注。本文将探讨如何设计和实现智慧交通平台的系统架构,以应对日益增长的城市交通需求,并提高交通管理的智能化水平。 ### 1. 智慧…...
移动端设置position: fixed;固定定位,底部出现一条缝隙,不知原因,欢迎探讨!!!
1、问题 在父盒子中有一个子盒子,父盒子加了固定定位,需要子盒子上下都有要边距,用margin或者padding挤开时,会出现缝隙是子盒子背景颜色的。 测试过了,有些手机型号有,有些没有,微信小程序同移…...
有关网络安全的课程学习网页
1.思科网络学院 免费学习skillsforall的课程 课程链接:Introduction to Cybersecurity by Cisco: Free Online Course (skillsforall.com) 2.斯坦福大学计算机和网络安全基础 该证书对于初学者来说最有价值,它由最著名的大学之一斯坦福大学提供。您可…...
计算机网络-面试题
一、基础 1、网络编程 网络编程的本质是多台计算机之间的数据交换存在问题 如何准确的定位网络上一台或多台主机如何进行可靠传输2、网络协议 在计算机网络有序的交换数据,就必须遵守一些事先约定好的规则,比如交换数据的格式、是否需要发送一个应答信息。这些规则被称为网络…...
C++虚函数
C虚函数 在C中,虚函数(Virtual Function)是一个使用关键字virtual声明的成员函数,它在基类中被声明,以便在任何派生类中被重写(Override)。使用虚函数的目的是实现多态性——一种允许使用基类指…...
MySQL数据库基础(二):MySQL数据库介绍
文章目录 MySQL数据库介绍 一、MySQL介绍 二、MySQL的特点 三、MySQL版本 四、MySQL数据库下载与安装 1、下载 2、安装 五、添加环境变量(Windows) 六、检测环境变量是否配置成功 MySQL数据库介绍 一、MySQL介绍 MySQL是一个关系型数据库管理…...