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…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
