代码随想录算法训练营第三天 | 链表理论基础,203.移除链表元素,707.设计链表,206.反转链表
对于链表完全陌生,但是看题目又觉得和数组一样的
链表理论基础
Q:什么是链表?
A:链表是由一系列结点组成的。每一个结点由两部分组成:数据和指针。
203.移除链表元素
题目:
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
示例 2:
输入:head = [], val = 1
输出:[]
示例 3:
输入:head = [7,7,7,7], val = 7
输出:[]
思路:
需要遍历,当元素等于val,指针指向下下个元素的。第一次学习并使用链表,需要熟悉如何建立链表,如何遍历元素。所以一刷基本属于照猫画虎,但是重要的掌握思路,我也不求一遍就通透。
代码:
# Definition for singly-linked list. 定义单链表
# class ListNode: 定义链表的类
# def __init__(self, val=0, next=None):
# 链表中的数据和指针,next=None是最后一个结点的属性,即指针指向空\
# 但是在此处,有2种指向:如果有下一个结点,可以再给next赋值,没有就让它默认指向空
# self.val = val
# self.next = next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:# 创建虚拟头部节点,简化删除过程,因为有可能第一个结点就需要删除dummy_head = ListNode(next=head)# 遍历链表,删除val的值cur = dummy_headwhile cur.next: # 只要当前结点的下一个结点不为空,就循环if cur.next.val == val:cur.next = cur.next.next # 跳过val值,也就是删除该值的动作else:cur = cur.next # 如果不等与val,继续遍历return dummy_head.next # 返回虚拟头节点的指针,也就是去除了val值的新链表
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
思路:
这道题目非常经典,涵盖了链表基本的操作。题目看起来复杂,基本是如下几个问题:
- 在头部插入新节点
- 在尾部插入新节点
- 在中间插入新节点
- 删除指定的结点
卡哥强调:需要注意的是新增结点的时候,要让新结点先指向下一个结点,再让上一个结点指向新节点,顺序很重要。
代码:
1、单链表
# 定义一个链表:
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList: # 单链表# 初始化链表def __init__(self):self.dummy_head = ListNode() # 建立虚拟节点self.size = 0 # 初始化结点的长度为0,也就是刚开始链表没有任何数字# 获取下标的值def get(self, index: int) -> int:if index < 0 or index >= self.size: # 在链表之外的范围,不符合return -1cur = self.dummy_head.next # 必须要用self,for i in range(index):cur = cur.next # 表示将指针移动到下一个结点return cur.val# 在头部新增一个结点def addAtHead(self, val: int) -> None:self.dummy_head.next =ListNode(val,self.dummy_head.next) # 虚拟结点指向新节点self.size += 1## 在头部新增一个结点# 加入自己理解写的,看下来和双链表比较接近# def addAtHead(self, val: int) -> None:# new_node = ListNode(val) # 创建新节点# new_node.next = self.dummy_head.next # 新节点指向头节点# self.dummy_head.next = new_node # 虚拟结点指向新节点# self.size += 1# 在尾部添加一个结点def addAtTail(self, val: int) -> None:# new_node_tail = ListNode(val)cur = self.dummy_head # 指针当前指向虚拟节点while cur.next: # 当当前指针没有指向空,则一直循环cur = cur.nextcur.next = ListNode(val)self.size += 1# 在指定下标添加一个结点def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returncur = self.dummy_head# new_node3 = ListNode(val)for i in range(index):cur = cur.nextcur.next = ListNode(val,cur.next)self.size += 1# 删除指定下标的结点def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size: # 这里的'='非常重要!debug了很久很久……returncur = self.dummy_headfor i in range(index):cur = cur.next # 在链表中遍历至索引位置的前一个结点cur.next = cur.next.next # index这个位置的数就等于它的下一个数,就实现了删除index指向的数self.size -= 1# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)class MyLinkedList:
2、双链表
……暂时还不能完全理解双链表,先把单链表学会了再来……
【总结】
链表的基本操作和思路已经理解,但是一些临界的条件考虑的还不够周全,甚至写起代码相当生涩。继续加油吧!
206.反转链表
题目:
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
思路:
让每一个结点的指针指向前一个结点。
代码:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:prev=None # 前一个结点cur=head # 当前结点next=None # 下一个结点while cur:next=cur.nextcur.next=prev # 实现反转prev=curcur=nextreturn prev
今日总结:
学到新知识的感觉很踏实,但是一次也没有办法消化三道题,对我来说,在学习的过程中手写是很有用的,学习到链表的基础知识并在做题中了解逻辑,明日继续加油!
相关文章:
代码随想录算法训练营第三天 | 链表理论基础,203.移除链表元素,707.设计链表,206.反转链表
对于链表完全陌生,但是看题目又觉得和数组一样的 链表理论基础 Q:什么是链表? A:链表是由一系列结点组成的。每一个结点由两部分组成:数据和指针。 203.移除链表元素 题目: 给你一个链表的头节点 head 和…...
如何利用仪表构造InfiniBand流量在数据中心测试中的应用
一、什么是Infiniband? 在当今数据爆炸的时代,数据中心作为信息处理的中心枢纽,面临着前所未有的挑战。传统的通信方式已经难以满足日益增长的数据传输需求,而InfiniBand技术的出现,为数据中心带来了全新的通信解决方…...
Kubernetes 文档 / 概念 / Kubernetes 架构 / 节点
Kubernetes 文档 / 概念 / Kubernetes 架构 / 节点 此文档从 Kubernetes 官网摘录 中文地址 英文地址 节点上的组件包括 kubelet、 容器运行时以及 kube-proxy。 管理 向 API 服务器添加节点的方式主要有两种: 节点上的 kubelet 向控制面执行自注册;…...
ICode国际青少年编程竞赛- Python-1级训练场-for循环练习
ICode国际青少年编程竞赛- Python-1级训练场-for循环练习 1、 for i in range(3):Dev.step(4)Dev.turnLeft()2、 for i in range(3):Dev.step(2)Dev.turnRight()Dev.step(2)Dev.turnLeft()3、 for i in range(3):Dev.step(2)Dev.turnRight()Dev.step(2)Dev.turnLeft()4、 for…...
Flutter分模块开发、模块可单独启动、包含Provider
前言 当前案例 Flutter SDK版本:3.13.2 目前Flutter都是在一个项目中,创建不同目录进行模块开发,我进行Android原生开发时,发现原生端,是可以将每个模块独立运行起来的,灵感来自这; 折腾了几…...
Element-UI快速入门:构建优雅的Vue.js应用界面
Element-UI是一套基于Vue.js的组件库,提供了丰富的UI组件和交互效果,帮助开发者快速构建出美观、功能丰富的Web应用界面。本文将介绍如何快速入门Element-UI,并搭建一个简单的示例界面。 步骤一:安装Element-UI 首先,…...
Flutter 中的 @immutable:深入解析与最佳实践
在 Flutter 开发中,immutable 注释扮演着至关重要的角色,用于标记不可变类。不可变类顾名思义,其状态一旦创建便不可更改,这与可变类截然不同。后者允许在创建后对实例进行修改。 immutable 的利好 引入不可变类可以带来诸多优势…...
Pandas数据可视化 - Matplotlib、Seaborn、Pandas Plot、Plotly
可视化工具介绍 让我们一起探讨Matplotlib、Seaborn、Pandas Plot和Plotly这四个数据可视化库的优缺点以及各自的适用场景。这有助于你根据不同的需求选择合适的工具。 1. Matplotlib 优点: 功能强大:几乎可以用于绘制任何静态、动画和交互式图表。高度可定制&a…...
人工智能的发展将如何重塑网络安全
微信搜索关注公众号网络研究观,获取更多信息。 人们很容易认为人工智能 (AI) 真正出现是在 2019 年,当时 OpenAI 推出了 ChatGPT 的前身 GPT-2。 但现实却有些不同。人工智能的基础可以追溯到 1950 年,当时数学家艾伦图灵发表了题为“计算机…...
Prometheus+Grafana多方位监控
PrometheusGrafana多方位监控 契机 ⚙ 最近发现火山引擎有托管的Prometheus,可是当前是邀测阶段。并且发现火山云的ECS是自带开机自启的exporter的。刚好需要搭建一套服务器监控,所以研究了一套Prometheus监控,包含linux主机监控nginx监控es监控rabbitM…...
使用Docker安装Redis
大家好,今天给大家分享一下如何使用docker安装Redis,关于docker的安装和常用命令,大家可以参考下面两篇文章,本文中不做过多描述。 Docker在Windows与CentOS上的安装 Docker常用命令 关于Redis的介绍与常用操作可以参考&#x…...
React 之 Effect与事件(event)(八)
Effect(useEffect Hook) 在React中,Effect(或者更具体地说,useEffect Hook)是一个特殊的函数,它允许你在函数组件中执行副作用操作。这些副作用操作可能包括数据获取、手动更改DOM、订阅或取消订…...
网卡的了解
什么是网卡_csdn网卡是什么-CSDN博客 MAC地址:48位串行号(独一无二) 2^48281 474 976 710 656 10位:10亿 5位:1万 15位:10万亿 网卡就是网络适配器 设置--->网络和Internet--->高级网络设置--->硬…...
SSM框架目录
ssm 知识相关目录主要参考尚硅谷 赵伟风老师的视屏,参考链接为 SSM视频_ SSM技术视频_SSM视频教程_尚硅谷 【注意】有些图片为了简便,所以就直接使用了视屏分析。 1、SSM框架相关知识 SpringFramework 基本概念 链接:SpringFramework 基本…...
MATLAB实现杜拉德公式和凯夫公式的计算固液混合料浆临界流速
MATLAB实现杜拉德公式和凯夫公式的计算固液混合料浆临界流速: 杜拉德公式是用来计算非均质固液混合料浆在输送管中的临界速度的公式,具体形式为: uL FL (2gD / (ρ0 - ρ1))^(1/2) 其中: uL:表示料浆的临界速度,…...
Oceanbase all-in-one单机版部署,通过MySQL客户端连接OB租户,DBEAVER 客户端连接MySQL租户。
一.Oceanbase all-in-one单机版部署 1.修改资源限制。 vim /etc/security/limits.conf root soft nofile 655350 root hard nofile 655350 * soft nofile 655350 * hard nofile 655350 * soft stack unlimited * hard stack unlimited * soft nproc 655360 * hard nproc 6553…...
【DevOps】玩转 Google Cloud:项目切换与 K8s 集群访问
本篇博文将带您深入了解 Google Cloud Platform (GCP) 项目管理和 Kubernetes 集群访问的实用技巧。无论您是 GCP 新手还是经验丰富的云端开发者,都能从中获益匪浅。 目录 一、查看 Google Cloud 项目列表 方法一:使用 gcloud 命令行工具 方法二...
大模型_DISC-MedLLM基于Baichuan-13B-Base医疗健康对话
文章目录 DISC-MedLLM介绍概述数据集部署推理流程 DISC-MedLLM 介绍 DISC-MedLLM 是一个专门针对医疗健康对话式场景而设计的医疗领域大模型,由复旦大学数据智能与社会计算实验室 (Fudan-DISC) 开发并开源。 该项目包含下列开源资源: DISC-Med-SFT 数据集 (不包…...
开源模型 Prometheus 2 能够评估其他语言模型,其效果几乎与 GPT-4 相当
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
【Java】HOT100 贪心算法
目录 理论基础 一、简单贪心 LeetCode455:分发饼干 二、中等贪心 2.1 序列问题 LeetCode376:摆动序列 2.2 贪心股票问题 LeetCode121:买卖股票的最佳时机 LeetCode121:买卖股票的最佳时机ii 2.3 两个维度权衡问题 LeetCode135&…...
绝地求生:PUBG杜卡迪联名进入倒计时3天!
大家好,我是闲游盒。 杜卡迪联名已经进入倒计时3天!喜欢的朋友要注意结束时间可千万别错过! 杜卡迪6色车辆 随着五一小长假的结束,本次混沌漫彩通行证也即将结束,本次通行证31级之后没升1级可额外领取1500BP和挑战者纪…...
【论文阅读】Learning Texture Transformer Network for Image Super-Resolution
Learning Texture Transformer Network for Image Super-Resolution 论文地址Abstract1. 简介2.相关工作2.1单图像超分辨率2.2 Reference-based Image Super-Resolution 3. 方法3.1. Texture TransformerLearnable Texture Extractor 可学习的纹理提取器。Relevance Embedding.…...
读字库写FM24C04
/*PCB机板增加读写24C64函数PAST 2017 12 26 08:10 CODE 7382*/ /*按11键进入手动选择,按12键进入参数设定界面 按1存1 2存2 3存3 15存0 16存1236 17读EEPROM显示正确 L1008 13775061792 ******/ #include <reg52.h>…...
boost::asio::ip::tcp::socket set_option
Boost asio 官方教程简介_asio::write-CSDN博客 boost::asio::ip::tcp::socket 是一个用于异步I/O操作的类,它是Boost.Asio库的一部分,专门用于处理TCP套接字。 以下是一个简单的使用 boost::asio::ip::tcp::socket 的例子,这个例子展示了如…...
华为鸿蒙HarmonyOS应用开发者高级认证答案
判断 1只要使用端云一体化的云端资源就需要支付费用(错) 2所有使用Component修饰的自定义组件都支持onPageShow,onBackPress和onPageHide生命周期函数。(错) 3 HarmonyOS应用可以兼容OpenHarmony生态(对…...
ElasticSearch 与 OpenSearch:拉开性能差距
Elasticsearch 与 OpenSearch:扩大性能差距 对于任何依赖快速、准确搜索数据的组织来说,强大、快速且高效的搜索引擎是至关重要的元素。对于开发人员和架构师来说,选择正确的搜索平台可以极大地影响您的组织提供快速且相关结果的能力。在我们…...
Java构造器
构造器 无参构造器有参构造器构造方法VS成员方法总结 概念:也称构造方法、构造函数。作用是构造出来一个类的实例,确保对象得到初始化。 格式: 权限修饰符 类名(无参/有参){ }。 分类: 带参数:有参构造器不带参数&am…...
TiDB系列之:使用TiUP部署TiDB集群最新版本,同时部署TiCDC的详细步骤
TiDB系列之:使用TiUP部署TiDB集群最新版本,同时部署TiCDC的详细步骤 一、部署TiDB集群二、准备环境三、安装 TiUP四、安装TiUP cluster组件五、初始化包含TiCDC的TiDB集群拓扑文件六、检查和修复集群存在的潜在风险七、查看可以安装的tidb版本八、部署 TiDB 集群:九、查看集…...
【经典算法】LeetCode 72. 编辑距离(Java/C/Python3/Go实现含注释说明,中等)
题目描述 给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数。 你可以对一个单词进行如下三种操作: 插入一个字符删除一个字符替换一个字符 原题:LeetCode 72 思路及实现 方式一:动态规划 思路…...
webstorm 常用插件
安装插件步骤: 打开软件,文件 -- 设置-- 插件 -- 输入插件名称 -- 安装 代码截图: code screenShots 先选中代码,按 ctrl shift alt a,就可截取选中的代码颜色注释: comments highlighter 对注释的文字改变颜色高亮成对符号: h…...
淄博哪个网站做房屋出赁好/2023年火爆的新闻
112.路径总和 437. 路径总和 III 题目–112.路径总和 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目…...
电子商务网站建设作文/信息流优化师怎么入行
Given an input string, reverse the string word by word.For example,Given s "the sky is blue",return "blue is sky the".题目比较简单,就是倒置一下字符串。中间说的几个细节,开头,末尾,包括中间都可能…...
软装包括哪些/手机优化软件排名
开头 昨天去面了一家公司,价值观有受到冲击。 面试官技术方面没的说,他可能是个完美主义的人,无论什么事情到了他那里好像都有解决的方案,我被说的无所适从,感觉他很厉害。 但我不能认可的是,面试官觉得…...
网站设计策划书/搜索seo神器
未选择的路 黄色的树林里分出两条路 可惜我不能同时去涉足 我在那路口久久伫立 我向着一条路极目望去 直到它消失在丛林深处 但我却选择了另外一条路 它荒草萋萋,十分幽寂 显得更诱人,更美丽 虽然在这条小路上 很少留下旅人的足迹 那天清晨落…...
网站的地图要怎么做/网络营销课程培训课程
1.持久化简介 数据持久化就是指将那些内存中的瞬时数据保存到储存设备中,保证即使在手机或电脑关机的情况下,这些数据仍然不会丢失.保存在内存中的数据是处于瞬时状态的,而保存在存储设备中的数据是处于持久状态的,持久化技术提供了一种机制可以让数据在瞬时状态和持久状态直接…...
网站建设内容/百度工具seo
绑定: * 绑定 * param {哪一个元素对象} ele * param {什么事件类型} type * param {触发函数} fun */ function addEvent(ele,type,fun){if(ele.addEventListener){//标准浏览器ele.addEventListener(type,fun);}else{//IE8-浏览器ele.attachEvent(ontype,fun)}…...