leetcode--设计链表
707.设计链表
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:
val和next。val是当前节点的值,next是指向下一个节点的指针/引用。如果是双向链表,则还需要属性
prev以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。实现
MyLinkedList类:
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效,则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度,那么该节点会被追加到链表的末尾。如果index比长度更大,该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效,则删除链表中下标为index的节点。示例:
输入 ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 输出 [null, null, null, null, 2, null, 3]解释 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 现在,链表变为 1->3 myLinkedList.get(1); // 返回 3提示:
0 <= index, val <= 1000- 请不要使用内置的 LinkedList 库。
- 调用
get、addAtHead、addAtTail、addAtIndex和deleteAtIndex的次数不超过2000。
单链表
// 定义链表节点类
class ListNode {int val; // 节点存储的值ListNode next; // 指向下一个节点的指针// 无参构造方法ListNode() {}// 带参数构造方法ListNode(int val) {this.val = val;}
}// 实现单链表的类
class MyLinkedList {int size; // 链表的长度(节点数)ListNode head; // 虚拟头节点,方便统一操作// 初始化链表MyLinkedList() {head = new ListNode(0); // 初始化虚拟头节点size = 0; // 初始化链表长度为 0}// 获取指定索引处的值public int get(int index) {// 如果索引非法,返回 -1if (index < 0 || index >= size) {return -1;}// 从虚拟头节点的下一个节点开始遍历ListNode cur = head.next;for (int i = 0; i < index; i++) {cur = cur.next; // 移动到下一个节点}// 返回指定节点的值return cur.val;}// 在链表头部插入值为 val 的节点public void addAtHead(int val) {// 创建新节点ListNode cur = new ListNode(val);// 新节点的 next 指向当前链表的第一个节点cur.next = head.next;// 虚拟头节点的 next 指向新节点head.next = cur;// 链表长度加 1size++;}// 在链表尾部插入值为 val 的节点public void addAtTail(int val) {// 创建新节点ListNode cur = head; // 从虚拟头节点开始遍历ListNode tail = new ListNode(val); // 新的尾部节点// 遍历链表找到最后一个节点for (int i = 0; i < size; i++) {cur = cur.next;}// 将最后一个节点的 next 指向新节点cur.next = tail;// 链表长度加 1size++;}// 在指定索引处插入值为 val 的节点public void addAtIndex(int index, int val) {// 如果索引超过当前链表长度,不进行插入操作if (index > size) {return;}// 如果索引小于 0,将索引置为 0if (index < 0) {index = 0;}// 创建新节点ListNode cur = head; // 从虚拟头节点开始遍历ListNode addNode = new ListNode(val); // 要插入的节点// 遍历到指定索引位置的前一个节点for (int i = 0; i < index; i++) {cur = cur.next;}// 插入新节点addNode.next = cur.next; // 新节点的 next 指向当前索引位置的节点cur.next = addNode; // 当前节点的 next 指向新节点size++; // 链表长度加 1}// 删除指定索引处的节点public void deleteAtIndex(int index) {// 如果索引非法,不进行删除操作if (index < 0 || index >= size) {return;}// 从虚拟头节点开始遍历ListNode cur = head;// 遍历到指定索引位置的前一个节点for (int i = 0; i < index; i++) {cur = cur.next;}// 删除节点:当前节点的 next 指向被删除节点的下一个节点cur.next = cur.next.next;size--; // 链表长度减 1}
}
双链表
class ListDoubleNode{int val;ListDoubleNode prev,next;ListDoubleNode(){};ListDoubleNode(int val){this.val=val;};
}
class MyLinkedListSolution1 {int size;ListDoubleNode head,tail;public MyLinkedListSolution1() {//初始化操作this.size = 0;this.head = new ListDoubleNode(0);this.tail = new ListDoubleNode(0);//这一步非常关键,否则在加入头结点的操作中会出现null.next的错误!!!head.next=tail;tail.prev=head;}public int get(int index) {//判断index是否有效if(index>=size){return -1;}ListDoubleNode cur = this.head;//判断是哪一边遍历时间更短if(index >= size / 2){//tail开始cur = tail;for(int i=0; i< size-index; i++){cur = cur.prev;}}else{for(int i=0; i<= index; i++){cur = cur.next;}}return cur.val;}public void addAtHead(int val) {//等价于在第0个元素前添加addAtIndex(0,val);}public void addAtTail(int val) {//等价于在最后一个元素(null)前添加addAtIndex(size,val);}public void addAtIndex(int index, int val) {//index大于链表长度if(index>size){return;}size++;//找到前驱ListDoubleNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}//新建结点ListDoubleNode newNode = new ListDoubleNode(val);newNode.next = pre.next;pre.next.prev = newNode;newNode.prev = pre;pre.next = newNode;}public void deleteAtIndex(int index) {//判断索引是否有效if(index>=size){return;}//删除操作size--;ListDoubleNode pre = this.head;for(int i=0; i<index; i++){pre = pre.next;}pre.next.next.prev = pre;pre.next = pre.next.next;}
}
相关文章:
leetcode--设计链表
707.设计链表 你可以选择使用单链表或者双链表,设计并实现自己的链表。 单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。 如果是双向链表,则还需要属性 prev 以指示链表中的…...
【MySQL】:数据库操作
MySQL 数据库基础理论 2.1 数据库系统概述 介绍数据库系统的基本概念、发展历程、分类及 MySQL 在其中的地位与特点。 2.2 MySQL 数据库体系结构 解析 MySQL 的整体架构,包括服务器层与存储引擎层的功能与交互机制,重点探讨 InnoDB、MyISAM 等存…...
刷蓝桥杯历年考题(更新至15届~)
第十五届 CA组省赛 AcWing5980.训练士兵 方法一:树状数组:O(nlogn) self-complete /*先枚举组团,后分析每个士兵,有一个特点,组团费用是固定的,那当然是让所有士兵一块训练,训练完的士兵也不会有损失当还…...
AI与BI的火花:大语言模型如何重塑商业智能的未来
大家好,我是独孤风。 在当今这个数据驱动的时代,企业对于信息的需求如同对于氧气的需求一般至关重要。商业智能(BI)作为企业获取、分析和呈现数据的关键工具,正在经历一场深刻的变革,而这一变革的催化剂正是…...
Qt 详解QtNFC 读写模式
文章目录 Qt NFC 读写模式详解1. NFC 读写模式简介1.1 什么是 NFC 读写模式?主要功能: 1.2 常见应用场景 2. Qt NFC 读写模式原理3. 配置 QtNFC 模块4. NFC 读写操作实现4.1 NFC 标签读取代码示例功能解析 4.2 NFC 标签写入代码示例功能解析 5. 使用注意…...
增删改查文档
列表 : 列表包含 : 模糊查找 分页 列表jsp页面 : 一 :导入外部文件 (举例 : 用户点进来就可以看到菜单,这是预加载属于,使用文档就绪函数实现) 二 : body 上 ① : 文档就绪函数 ${ function() //获取条件查询的字段 //组装对象 //调用文档就绪函数 } ② : 封装ajax方…...
C语言蓝桥杯2023年省赛真题
文章目录 持续更新中...第一题题目描述输入格式输出格式样例输出提示 2 第二题题目描述 第三题题目描述输入格式输出格式样例输入样例输出 第四题题目描述输入格式输出格式样例输入样例输出提示 第四题题目描述输入格式输出格式样例输入样例输出提示 第五题题目描述输入格式输出…...
Python迭代器-大数据量的处理
一 生成器的实际使用(大量数据的导出) #分批导出数据然后分批写入excel import pandas as pd import openpyxl from openpyxl.utils.dataframe import dataframe_to_rowsdef execute_query(query):# 假设这是执行 SQL 查询的函数# 返回查询结果passdef …...
自动化包括态交互与感交互,而智能化包括势交互与知交互
“自动化包括态交互与感交互,而智能化包括势交互与知交互”交互框架将交互过程划分为不同类型,有助于更清晰地理解自动化和智能化的本质及其在未来agent应用中的差异与联系。 1. 自动化:态交互与感交互 自动化主要关注的是高效、无差错地执行…...
VideoBooth: Diffusion-based Video Generation with Image Prompts
VideoBooth: Diffusion-based Video Generation with Image Prompts 概括 文章提出了一个视频生成模型VideoBooth,输入一张图片和一个文本提示词,即可输出保持图片中物体且符合文本提示词要求的视频。 方法 粗-细两阶段设计:1)…...
模拟简单的iOT工作流
没有实际接触过iOT的流程,应该实际使用比这个接口返回要复杂,只是演示~希望能参与实际的接口接入,而不是只展示个假数据。 启动RabbitQ 使用的是3.8.5 启动命令 RabbitMQ Service - start RabbitMQ Command Prompt rabbitmqctl start_app …...
C++学习0.2: RAII
引用: 【代码质量】RAII在C编程中的必要性_raii 在c中的重要性-CSDN博客 C RAII典型应用之lock_guard和unique_lock模板_raii lock-CSDN博客 前言: 常用的线程间同步/通信(IPC)方式有锁(互斥锁、读写锁、自旋锁)、…...
k8s,进一步理解Pod
比如,凡是调度、网络、存储,以及安全相关的属性,基本上是Pod 级别的。 这些属性的共同特征是,它们描述的是“机器”这个整体,而不是里面运行的“程序”。比如,配置这个“机器”的网卡(即&#…...
MFC图形函数学习13——在图形界面输出文字
本篇是图形函数学习的最后一篇,相关内容暂告一段落。 在图形界面输出文字,涉及文字字体、大小、颜色、背景、显示等问题,完成这些需要系列函数的支持。下面做简要介绍。 一、输出文本函数 原型:virtual BOOL te…...
【Canvas与雷达】点鼠标可暂停金边蓝屏雷达显示屏
【成图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>点鼠标可暂停金边蓝屏雷达显示屏 Draft1</title><style typ…...
React第十二节组件之间通讯之发布订阅模式(使用pubsub-js插件)
组件之间通讯常用方案 1、通过props 2、通过context 3、通过发布订阅模式 4、通过Redux 后面会有专栏介绍 1、安装 pubsub-js 插件 yarn add pubsub-js 常用的事件 a、发布事件:传入一个自定义事件名称(name),以及要发布的消息内…...
Vue3安装 运行教程
本文是综合了所有vue安装教程而成 更细化 更简略 希望对各位读者有所帮助! Vue安装 1. Vue-cli脚手架安装 安装vue的方式有很多 我们这里选择npm方式安装vue npm方式 npm方式安装vue,详细介绍见下文。 1.node.js安装和配置 安装npm 需要安装note.js&…...
MySQL:约束constraint
约束就是表中数据的限制条件. 表在设计的时候加入约束的目的是为了保证表中记录的完整性和有效性,如用户表有些列的值(手机号)不能为空,有些列的值(身份证号)不能重复。 主键约束(primary key) PK MySQL主…...
使用Rufus制作Ubuntu需要注意
在使用Rufus制作Ubuntu启动盘并进行BIOS设置时,需要注意以下几点: 关闭RST(英特尔 快速存储技术):在BIOS设置中,如果电脑启用了RST功能,需要将其关闭。因为Ubuntu可能无法检测到硬盘&a…...
探索Go语言的高级特性:性能分析与安全性
Go语言性能分析与安全性 引言 Go语言因其高效的并发特性、简洁的语法和强大的工具链而受到广泛欢迎。在实际开发中,性能分析和安全性是需要特别关注的两个方面。本文将深入探讨Go语言中的性能分析工具和安全性考虑,帮助开发者编写高效、安全的Go应用程…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
