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

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...