当前位置: 首页 > 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...