当前位置: 首页 > news >正文

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)
    • 维护一个有序单链表,当有新的数据被访问时,从链表头开始遍历链表:
      1. 若链表中存在新数据,将其删除,插入到链表头
      2. 若链表中不存在新数据:
        • 若缓存未满,将新数据插入到链表头
        • 若缓存已满,删除链表尾结点,将新数据插入到链表头
  • 链表代码书写的注意事项:
    • 警惕指针丢失和内存泄漏
      • 插入节点时,注意操作顺序
      • 删除链表结点时,手动释放内存空间
    • 利用哨兵简化实现难度
      • 针对链表的插入和删除操作,需要对插入第一个结点和删除最后一个节点的情况进行特殊处理
      • 引入头结点,将head指针始终指向头结点,头结点指向第一个数据节点
    • 边界条件处理
      • 链表为空时
      • 链表只包含一个节点时
      • 链表只包含两个节点时
      • 操作头结点和尾结点时
    • 举例画图,辅助思考
  • 5个常见的链表操作
    • 单链表反转(分别使用迭代和递归实现)
    • 链表中环的检测(迭代实现和快慢指针实现)
    • 两个有序的链表合并(常规解法和递归解法)
    • 删除链表倒数第n个结点(单指针两次遍历和双指针一次遍历)
    • 求链表的中间节点(单指针两次遍历和双指针一次遍历)

相关文章:

leetcode-链表类题目

文章目录 链表(Linked List) 链表(Linked List) 定义:链表(Linked List)是一种线性表数据结构,他用一组任意的存储单元来存储数据,同时存储当前数据元素的直接后继元素所…...

数据结构——哈希

哈希表 是一种使用哈希函数组织数据的数据结构,它支持快速插入和搜索。 哈希表(又称散列表)的原理为:借助 哈希函数,将键映射到存储桶地址。更确切地说, 1.首先开辟一定长度的,具有连续物理地址…...

效果好的it监控系统特点

一个好的IT监控系统应该具备以下特点:  全面性:IT监控系统应该能够监视和管理IT系统的所有方面,包括网络、服务器、应用程序和数据库等。这样可以确保系统的各个方面都得到充分的监视和管理。  可靠性:IT监控系统需要保持高可…...

leetcode1288. 删除被覆盖区间(java)

删除被覆盖区间 题目描述贪心法代码演示 题目描述 难度 - 中等 leetcode1288. 删除被覆盖区间 给你一个区间列表&#xff0c;请你删除列表中被其他区间所覆盖的区间。 只有当 c < a 且 b < d 时&#xff0c;我们才认为区间 [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盘&#xff0c;需要在WSL2中创建一个目录挂载U盘 sudo mkdir /mnt/f sudo mount -t drvfs F: /mnt/f后续所有的操作都完成后&#xff0c;拔掉U盘前&#xff0c;可以使用下面的命令从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 推导式是一种独特的数据处理方式&#xff0c;可以从一个数据序列构建另一个新的数据序列的结构体。 Python 支持各种数据结构的推导式&#xff1a; 列表(list)推导式字典(dict)推导式集合(set)推导式元组(tuple)推导式 列表推导式 列表推导式格式为&…...

es6的新特性有哪些

ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript的一个重要版本&#xff0c;引入了许多新的语法和功能。以下是ES6的一些主要特性&#xff1a; 块级作用域&#xff08;Block Scope&#xff09;&#xff1a;引入了let和const关键字&#xff0c;可以在块级作用域中声明变…...

logstash 消费kafka数据,转发到tcp端口

1&#xff0c; logstash 配置文件 [roothost1: ] cat /opt/logstash/kafka-to-tcp.yml input { kafka {bootstrap_servers > "192.168.0.11:9092" #这里可以是kafka集群&#xff0c;如"192.168.149.101:9092,192.168.149.102:9092"consumer_threads &…...

航天智信:严控航天系统研发安全,助力建设“航天强国”

航天智信作为中国航天科工三院在信息装备领域“做大做强”的重要布局&#xff0c;主要从事系统运用与联合体系研究&#xff0c;复杂信息系统的顶层设计、总体论证及研制生产&#xff0c;提供体系级、系统级信息系统整体解决方案&#xff0c;以及信息安全系统的设计研发与集成验…...

阿里云2核4G服务器5M带宽五年租用价格表

阿里云2核4G服务器5M带宽可以选择轻量应用服务器或云服务器ECS&#xff0c;轻量2核4G4M带宽服务器297元一年&#xff0c;2核4G云服务器ECS可以选择计算型c7、c6或通用算力型u1实例等&#xff0c;买5年可以享受3折优惠&#xff0c;阿腾云分享阿里云服务器2核4G5M带宽五年费用表&…...

基于Laravel通用型内容建站企业官网系统源码 可免费商用

是一个基于 Laravel 企业内容建站系统。模块市场拥有丰富的功能应用&#xff0c;支持后台一键快速安装&#xff0c;让开发者能快的实现业务功能开发。 系统完全开源&#xff0c;免费且不限制商业使用 2023年08月23日增加了以下12个特性&#xff1a; [新功能] 手机端Banner支持…...

风力发电常见问题

目录 叶片失速 风力发电机失速状态是指风力发电机的叶片在高风速下无法继续提供升力&#xff0c;导致叶片停止旋转或减速旋转&#xff0c;从而降低了风力发电机的效率和发电能力。判断风力发电机是否处于失速状态通常可以通过以下方法&#xff1a; 监测风速&#xff1a;最简单…...

uniapp 解决跨域的问题

uniapp 解决跨域的问题 我真的是个 沙雕 找对了解决办法 写错了地方 "h5" : {"devServer" : {"disableHostCheck" : true,"https": false,"proxy" : {"/app" : {"target" : "https://192.16…...

Springboot GET和POST请求的常用参数获取方式

GET 使用RequestParam注解 可以在控制器方法的参数上使用RequestParam注解来获取请求中的参数值。例如&#xff1a; GetMapping("/example") public String example(RequestParam String param) {// 使用param参数的值return "Value of param: " param…...

项目(智慧教室)第四部分,页面交互功能

一。页面构思 1.标题栏 大标题&#xff1a;智慧教室管理系统 小标题&#xff1a;灯光&#xff0c;报警&#xff0c;风扇&#xff0c;温度&#xff0c;湿度&#xff0c;光照 2.样式设计 背景设置。字体设置&#xff08;字体大小&#xff0c;格式&#xff0c;颜色&#xff09; 3.…...

基于Matlab分析的电力系统可视化研究

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

MySQL为什么不推荐使用in

有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top 首发博客地址 系列文章地址 当使用IN语句时&#xff0c;MySQL可能会遇到以下问题&#xff1a; 索引问题&#xff1a;MySQL使用索引来加速查询&#x…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...