leetcode-链表类题目
文章目录
- 链表(Linked List)
链表(Linked List)
- 定义:链表(Linked List)是一种线性表数据结构,他用一组任意的存储单元来存储数据,同时存储当前数据元素的直接后继元素所存放的内存地址。
- 操作
- 插入和删除操作时间复杂度为O(1)
- 随机访问第k个元素的时间复杂度为O(n)
- 单链表:
- 实现:数据域data+指针域next
- 循环链表:
- 实现:尾结点指针指向头结点
- 优点:支持时间复杂度O(1)找到头结点
- 双向链表:
- 实现:数据域data+指针域prior和next
- 优点:支持时间复杂度O(1)找到前驱结点
- 数组VS链表
- 时间复杂度
- 数组随机访问O(1),插入删除O(n)
- 链表随机访问O(n),插入删除O(1)
- 访问效率
- 数组使用连续内存空间实现,可以借助CPU缓存机制预读数据,访问效率更高;
- 链表在内存中非连续存储,对CPU缓存不友好,无法有效预读
- 空间
- 数组大小固定,声明时需要指定其大小,可能出现内存不足或者浪费情况
- 链表天然支持动态扩容,没有空间浪费情况
- 时间复杂度
- 应用:使用链表实现LRU缓存淘汰算法
- 缓存:一种提高数据读取性能的技术,广泛应用于硬件设计,软件开发,如CPU缓存,数据库缓存,浏览器缓存。缓存大小有限,当缓存满时,需要使用缓存淘汰策略决定哪些数据被清理,哪些数据被保留
- 缓存淘汰策略指当缓存满时数据的清理顺序,包括先进先出策略(FIFO),最少使用策略(Least Frequently Used, LFU),最近最少使用策略(Least Recently Used, LRU)
- 维护一个有序单链表,当有新的数据被访问时,从链表头开始遍历链表:
- 若链表中存在新数据,将其删除,插入到链表头
- 若链表中不存在新数据:
- 若缓存未满,将新数据插入到链表头
- 若缓存已满,删除链表尾结点,将新数据插入到链表头
- 链表代码书写的注意事项:
- 警惕指针丢失和内存泄漏
- 插入节点时,注意操作顺序
- 删除链表结点时,手动释放内存空间
- 利用哨兵简化实现难度
- 针对链表的插入和删除操作,需要对插入第一个结点和删除最后一个节点的情况进行特殊处理
- 引入头结点,将head指针始终指向头结点,头结点指向第一个数据节点
- 边界条件处理
- 链表为空时
- 链表只包含一个节点时
- 链表只包含两个节点时
- 操作头结点和尾结点时
- 举例画图,辅助思考
- 警惕指针丢失和内存泄漏
- 5个常见的链表操作
- 单链表反转(分别使用迭代和递归实现)
- 链表中环的检测(迭代实现和快慢指针实现)
- 两个有序的链表合并(常规解法和递归解法)
- 删除链表倒数第n个结点(单指针两次遍历和双指针一次遍历)
- 求链表的中间节点(单指针两次遍历和双指针一次遍历)
相关文章:
leetcode-链表类题目
文章目录 链表(Linked List) 链表(Linked List) 定义:链表(Linked List)是一种线性表数据结构,他用一组任意的存储单元来存储数据,同时存储当前数据元素的直接后继元素所…...
数据结构——哈希
哈希表 是一种使用哈希函数组织数据的数据结构,它支持快速插入和搜索。 哈希表(又称散列表)的原理为:借助 哈希函数,将键映射到存储桶地址。更确切地说, 1.首先开辟一定长度的,具有连续物理地址…...
效果好的it监控系统特点
一个好的IT监控系统应该具备以下特点: 全面性:IT监控系统应该能够监视和管理IT系统的所有方面,包括网络、服务器、应用程序和数据库等。这样可以确保系统的各个方面都得到充分的监视和管理。 可靠性:IT监控系统需要保持高可…...
leetcode1288. 删除被覆盖区间(java)
删除被覆盖区间 题目描述贪心法代码演示 题目描述 难度 - 中等 leetcode1288. 删除被覆盖区间 给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。 只有当 c < a 且 b < d 时,我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 在完成所有删除操作…...
Python 虚拟环境相关命令
一 激活 在 cd venv/scripts 进入虚拟环境 执行命令 activate 1、创建虚拟环境 $ python -m venv 2、激活虚拟环境 $ source <venv>/bin/activate 3、关闭虚拟环境 $ deactivate...
使用U盘同步WSL2中的git项目
1、将U盘挂载到WSL2中 假设U盘在windows资源管理器中被识别为F盘,需要在WSL2中创建一个目录挂载U盘 sudo mkdir /mnt/f sudo mount -t drvfs F: /mnt/f后续所有的操作都完成后,拔掉U盘前,可以使用下面的命令从WSL2中安全的移除U盘 umount …...
Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装
Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装 目录 Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装 一、简单介绍 二、ControlNet 插件下载安装 三、ControlNet 插件模型下载安装 四、ControlNet 插件其他的下载安装方式 五、Co…...
CMAK学习
VS中的cmake_cmake vs_今天也要debug的博客-CSDN博客 利用vs2017 CMake开发跨平台C项目实战_cmake vs2017_神气爱哥的博客-CSDN博客 【【入门】在VS中使用CMake管理若干程序】https://www.bilibili.com/video/BV1iz4y117rZ?vd_source0aeb782d0b9c2e6b0e0cdea3e2121eba...
Python 推导式
Python 推导式 Python 推导式是一种独特的数据处理方式,可以从一个数据序列构建另一个新的数据序列的结构体。 Python 支持各种数据结构的推导式: 列表(list)推导式字典(dict)推导式集合(set)推导式元组(tuple)推导式 列表推导式 列表推导式格式为&…...
es6的新特性有哪些
ES6(ECMAScript 2015)是JavaScript的一个重要版本,引入了许多新的语法和功能。以下是ES6的一些主要特性: 块级作用域(Block Scope):引入了let和const关键字,可以在块级作用域中声明变…...
logstash 消费kafka数据,转发到tcp端口
1, logstash 配置文件 [roothost1: ] cat /opt/logstash/kafka-to-tcp.yml input { kafka {bootstrap_servers > "192.168.0.11:9092" #这里可以是kafka集群,如"192.168.149.101:9092,192.168.149.102:9092"consumer_threads &…...
航天智信:严控航天系统研发安全,助力建设“航天强国”
航天智信作为中国航天科工三院在信息装备领域“做大做强”的重要布局,主要从事系统运用与联合体系研究,复杂信息系统的顶层设计、总体论证及研制生产,提供体系级、系统级信息系统整体解决方案,以及信息安全系统的设计研发与集成验…...
阿里云2核4G服务器5M带宽五年租用价格表
阿里云2核4G服务器5M带宽可以选择轻量应用服务器或云服务器ECS,轻量2核4G4M带宽服务器297元一年,2核4G云服务器ECS可以选择计算型c7、c6或通用算力型u1实例等,买5年可以享受3折优惠,阿腾云分享阿里云服务器2核4G5M带宽五年费用表&…...
基于Laravel通用型内容建站企业官网系统源码 可免费商用
是一个基于 Laravel 企业内容建站系统。模块市场拥有丰富的功能应用,支持后台一键快速安装,让开发者能快的实现业务功能开发。 系统完全开源,免费且不限制商业使用 2023年08月23日增加了以下12个特性: [新功能] 手机端Banner支持…...
风力发电常见问题
目录 叶片失速 风力发电机失速状态是指风力发电机的叶片在高风速下无法继续提供升力,导致叶片停止旋转或减速旋转,从而降低了风力发电机的效率和发电能力。判断风力发电机是否处于失速状态通常可以通过以下方法: 监测风速:最简单…...
uniapp 解决跨域的问题
uniapp 解决跨域的问题 我真的是个 沙雕 找对了解决办法 写错了地方 "h5" : {"devServer" : {"disableHostCheck" : true,"https": false,"proxy" : {"/app" : {"target" : "https://192.16…...
Springboot GET和POST请求的常用参数获取方式
GET 使用RequestParam注解 可以在控制器方法的参数上使用RequestParam注解来获取请求中的参数值。例如: GetMapping("/example") public String example(RequestParam String param) {// 使用param参数的值return "Value of param: " param…...
项目(智慧教室)第四部分,页面交互功能
一。页面构思 1.标题栏 大标题:智慧教室管理系统 小标题:灯光,报警,风扇,温度,湿度,光照 2.样式设计 背景设置。字体设置(字体大小,格式,颜色) 3.…...
基于Matlab分析的电力系统可视化研究
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
MySQL为什么不推荐使用in
有的时候博客内容会有变动,首发博客是最新的,其他博客地址可能会未同步,认准https://blog.zysicyj.top 首发博客地址 系列文章地址 当使用IN语句时,MySQL可能会遇到以下问题: 索引问题:MySQL使用索引来加速查询&#x…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
