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

数据结构与算法 - 数组与二分查找 + Leetcode典型题

1. 什么是数组

数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
C++中二维数组在地址空间上也是连续的。

需注意:

  • 数组的下标从0开始。
  • 数组内存空间的地址是连续的。
  • 数组的元素是不能删的,只能覆盖。

2. 二分查找

力扣题目链接
之前的题解704. 二分查找中有一些地方不够清晰,此处补充说明。
数组为有序数组+数组中无重复元素 -> 考虑二分法

  1. 在计算mid时,考虑数据溢出的可能,应将mid = (low + high) / 2;写为
	int mid = left + ((right - left) / 2); //防止溢出
  1. 二分法根据选择的区间不同,有两种解决方式,分别为:左闭右闭 [left, right] 和左闭右开 [left, right)
  • 左闭右闭 [left, right] 的情况下,nums [right] 表示数组中最后一个元素,while (left <= right) 要使用 <= ,因为 left == right 是有意义的。且每次判断if (nums[mid] > target) 后,由于nums[mid] 一定不是target ,right 要赋值为 middle - 1,right = mid - 1;,这表示下一次要查找的左区间结束下标位置为 middle - 1,即区间为 [left, middle - 1]。
    同理,if (nums[mid] < target)时, left 要赋值为 middle + 1。

  • 左闭右开 [left, right) 的情况下,nums [right] 无意义,while (left < right)中使用**<**,因为 left == right 在区间 [left, right) 是没有意义的。每次判断if (nums[mid] > target) 后,nums[mid] 不等于target ,在左区间 [left, mid) 中继续寻找.
    区间右开:right更新为mid。
    区间左闭:if (nums[mid] < target)时,left 要更新为 mid + 1

  1. 二分查找时间复杂度为 O(log n)

相关题目1:35. 搜索插入位置
补充之前题解35. 搜索插入位置-二分查找中表达不清晰的地方。
这道题存在四种情况:

  1. 目标值在数组所有元素之前
  2. 目标值等于数组中某一个元素
  3. 目标值插入数组中的某一位置
  4. 目标值在数组所有元素之后

与上一道题的差别在于1,3,4情况下的返回值。在左闭右闭 [left, right] 的情况下,right = mid - 1;,(1情况下此时 right = -1;3情况下 right 指向应插入的前一个位置;4情况下 right 指向最后一个元素的位置)所以应返回 right + 1 ,即return right + 1;;在左闭右开 [left, right) 的情况下,right = mid;,所以应返回 right ,即return right;

相关题目2:69.x的平方根 367.有效的完全平方数
题解:【LeetCode-简单】69.x的平方根 + 367.有效的完全平方数 - 二分法

相关题目3:【LeetCode-中等】34. 在排序数组中查找元素的第一个和最后一个位置 - 二分法

3. 移除元素 - 双指针

力扣题目链接
题解:【LeetCode-简单】27.移除元素 - 数组与双指针法

由于Leetcode中数组是用的vector,这道题可以用nums.erase(it);函数暴力破解,但要注意erase()函数在删除元素后会将位于该元素后方的剩余元素前移,这将导致数组长度的改变以及后续元素下标的变化,删除元素后迭代器 it 不需要 it++便已经指向了下一个元素。

不考虑vector的因素,由于数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。本题可采用双指针的方法。

双指针法(快慢指针法): 通过一个快指针慢指针在一个for循环下完成两个for循环的工作。

下面定义本题中的快慢指针:

  • 快指针:寻找新数组(不含有目标元素的数组)的元素 ,即用于寻找不等于val的元素
  • 慢指针:指向更新新数组下标的位置,即指向需要被覆盖的等于val的元素

最终慢指针一定指向了最终数组末尾的下一个元素,只要返回慢指针即可。
题目中提及元素的顺序可以改变,同向双指针和相向双指针都可以使用,如果要求不能改变元素顺序,则应该使用同向双指针。

4. 有序数组的平方 - 双指针

力扣题目链接
典型的双指针问题,暴力解法的时间复杂度是O(nlogn),而采用双指针的时间复杂度是O(n)。
题解:【LeetCode-简单】977. 有序数组的平方-双指针

5. 长度最小的子数组 - 滑动窗口

力扣题目链接

题解:【LeetCode-中等】209.长度最小的子数组-双指针/滑动窗口

所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果

在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环完成了一个不断搜索区间的过程。滑动窗口只用一个for循环来完成这个操作。

而这个循环的索引,一定是表示 滑动窗口的终止位置

直观的动画演示:
请添加图片描述
滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

	while (sum >= s) {subLength = (j - i + 1); //取子序列的长度result = result < subLength ? result : subLength;这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)sum -= nums[i++]; }

6. 螺旋矩阵II - 模拟

力扣题目链接
题解:【LeetCode-中等】59.螺旋矩阵II - 二维数组

本题并不涉及到什么算法,就是模拟过程,还要注意边界情况。

相关文章:

数据结构与算法 - 数组与二分查找 + Leetcode典型题

1. 什么是数组 数组是存放在连续内存空间上的相同类型数据的集合。 数组可以方便的通过下标索引的方式获取到下标下对应的数据。 C中二维数组在地址空间上也是连续的。 需注意&#xff1a; 数组的下标从0开始。数组内存空间的地址是连续的。数组的元素是不能删的&#xff0c…...

SQL进阶(三):Join 小技巧:提升数据的处理速度

复杂数据结构处理&#xff1a;Join 小技巧&#xff1a;提升数据的处理速度 本文是在原本sql闯关的基础上总结得来&#xff0c;加入了自己的理解以及疑问解答&#xff08;by GPT4&#xff09; 原活动链接 用到的数据&#xff1a;链接 提取码&#xff1a;l03e 目录 1. 课前小问…...

开发知识点-.netC#图形用户界面开发之WPF

C#图形用户界面开发 NuGet框架简介WinForms(Windows Forms):WPF(Windows Presentation Foundation):UWP(Universal Windows Platform):MAUI(Multi-platform App UI):选择控件参考文章随笔分类 - WPF入门基础教程系列...

基于springboot实现流浪动物救助网站系统项目【项目源码+论文说明】

基于springboot实现流浪动物救助网站系统演示 摘要 然而随着生活的加快&#xff0c;也使很多潜在的危险日益突显出来&#xff0c;比如在各种地方会发现很多无家可归的、伤痕累累的、可怜兮兮的动物&#xff0c;当碰到这种情况&#xff0c;是否会立马伸出双手去帮助、救助它们&…...

灰度负载均衡和普通负载均衡有什么区别

灰度负载均衡&#xff08;Gray Load Balancing&#xff09;与普通负载均衡的主要区别在于它们服务发布和流量管理的方式。 灰度负载均衡 目的&#xff1a;主要用于灰度发布&#xff0c;即逐步向用户发布新版本的服务&#xff0c;以减少新版本可能带来的风险。工作方式&#x…...

【二分查找】朴素二分查找

二分查找 题目描述 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9…...

Windows Docker 部署 Redis

部署 Redis 打开 Docker Desktop&#xff0c;切换到 Linux 内核。然后在 PowerShell 执行下面命令&#xff0c;即可启动一个 redis 服务。这里安装的是 7.2.4 版本&#xff0c;如果需要安装其他或者最新版本&#xff0c;可以到 Docker Hub 中进行查找。 docker run -d --nam…...

什么是VR虚拟现实|虚拟科技博物馆|VR设备购买

虚拟现实&#xff08;Virtual Reality&#xff0c;简称VR&#xff09;是一种通过计算机技术模拟出的一种全新的人机交互方式。它可以通过专门的设备&#xff08;如头戴式显示器&#xff09;将用户带入一个计算机生成的虚拟环境之中&#xff0c;使用户能够与这个虚拟环境进行交互…...

高性能API云原生网关 APISIX安装与配置指南

Apache APISIX是Apache软件基金会下的顶级项目&#xff0c;由API7.ai开发并捐赠。它是一个高性能的云原生API网关&#xff0c;具有动态、实时等特点。 APISIX网关可作为所有业务的流量入口&#xff0c;为用户提供了丰富的功能&#xff0c;包括动态路由、动态上游、动态证书、A…...

Gradio Dataframe 学习笔记

Gradio Dataframe 学习笔记 0. 简介1. 使用场景2. 测试数据3. 学习代码4. 更多功能5. 学习资源6. 总结 0. 简介 Gradio是一个用于构建交互式机器学习界面的Python库。它可以轻松创建各种类型的界面&#xff0c;包括用于数据可视化和探索的界面。 Gradio Dataframe 组件是 Gra…...

深入理解计算机系统笔记

1.1 嵌套的数组 当我们创建数组的数组时&#xff0c;数组分配和引用的一般原则也是成立的。 例如&#xff0c;声明 int A[5][3]; 等价于下面的声明 typedef int row3_t[3]; row3_t A[5] 要访问多维数组的元素&#xff0c;编译器会以数组起始为基地址&#xff0c; (可能需…...

300分钟吃透分布式缓存(拉钩教育总结)

开篇寄语 开篇寄语&#xff1a;缓存&#xff0c;你真的用对了吗&#xff1f; 你好&#xff0c;我是你的缓存老师陈波&#xff0c;可能大家对我的网名 fishermen 会更熟悉。 我是资深老码农一枚&#xff0c;经历了新浪微博从起步到当前月活数亿用户的大型互联网系统的技术演进…...

2024亚马逊全球开店注册前需要准备什么?

在2023年出海四小龙SHEIN、Temu、速卖通AliExpress、TikTok Shop快速增长扩张&#xff0c;成为了中国跨境卖家“逃离亚马逊”的新选择。但是&#xff0c;跨境电商看亚马逊。当前&#xff0c;亚马逊仍然是跨境电商行业的绝对老大&#xff0c;占有将近70%成以上的业务份额。 作为…...

android Service 与 activity 通信 并不断传数据

注&#xff1a;这只是个Demo 以下载为案例&#xff0c;实现开启下载&#xff0c;暂停下载&#xff0c;下载进度不断发送给activity class DownloadService : Service() {override fun onBind(intent: Intent?): IBinder? {return MyBinder()}inner class MyBinder : Binder…...

Acwing-基础算法课笔记之数学知识(扩展欧几里得算法)

Acwing-基础算法课笔记之数学知识&#xff08;扩展欧几里得算法&#xff09; 一、扩展欧几里得算法1、裴蜀定理2、过程模拟3、代码模板 二、线性同余方程1、定义2、模拟过程3、结论证明 一、扩展欧几里得算法 1、裴蜀定理 对于任意正整数 a a a&#xff0c; b b b&#xff0…...

简单排列组合题(python版)

文章预览&#xff1a; 题目解法一输出结果 解法二输出结果输出结果 题目 有四个数字:1,2,3,4能组成多少个互不相同且无重复的数字的三位数? 各式多少? 解法一 我们粗略看一下这个题既然我们要组成三位数&#xff0c;那我们就循环3层每一层出一个数&#xff0c;并且if语句判…...

【排坑】搭建 Karmada 环境

git clone 报错 问题&#xff1a;Failed to connect to github.com port 443:connection timed out 解决&#xff1a; git config --global --unset http.proxy【hack/local-up-karmada.sh】 1. karmada ca-certificates (no such package) 问题&#xff1a;fetching http…...

每日一类:Qt GUI开发的基石《QWidget》

深入探索QWidget&#xff1a;Qt GUI开发的基石 在Qt框架中&#xff0c;QWidget类扮演着构建图形用户界面&#xff08;GUI&#xff09;的基础角色。它不仅提供了窗口的基本功能&#xff0c;还允许开发者通过继承和定制来创建各式各样的用户界面元素。本文将详细介绍QWidget的关…...

人大金仓与mysql的差异与替换

人大金仓中不能使用~下面的符号&#xff0c;字段中使用”&#xff0c;无法识别建表语句 创建表时语句中只定义字段名.字段类型.是否是否为空 Varchar类型改为varchar&#xff08;长度 char&#xff09; Int(0) 类型为int4 定义主键&#xff1a;CONSTRAINT 键名 主键类型&#x…...

Excel2LaTeX插件的使用、LaTeX表格

目录 一、下载Excel2Latex 二、使用Excel2Latex 1、将Excel2LaTeX文件添加到加载项 2、导出LaTex的表格数据 3、注意事项 1&#xff09;生成的latex表格断断续续问题 2&#xff09;改变线形的粗细 3&#xff09;表格太大&#xff0c;需要缩小到适应大小 4&#xff09;…...

从‘它怎么又挂了’到‘服务稳如狗’:我是如何用Docker给老旧Python项目续命的

从“它怎么又挂了”到“服务稳如狗”&#xff1a;我是如何用Docker给老旧Python项目续命的 三年前接手这个“祖传”Django 1.11项目时&#xff0c;我天真地以为最大的挑战是理解那些写满魔法方法的代码。直到第一次在生产环境部署——pip install 报错、ImportError 连环出现、…...

实测对比:EfficientNet-lite4在树莓派4B与Jetson Nano上的推理性能到底差多少?

EfficientNet-lite4边缘计算实战&#xff1a;树莓派4B与Jetson Nano推理性能深度对比 当你在树莓派上跑通第一个图像分类模型时&#xff0c;那种成就感就像在乐高积木上搭建出微型超级计算机。但当你发现实际部署需要兼顾速度、精度和功耗时&#xff0c;问题就变得复杂起来——…...

还在为Obsidian表格烦恼吗?这个Excel插件让你3分钟告别数据割裂

还在为Obsidian表格烦恼吗&#xff1f;这个Excel插件让你3分钟告别数据割裂 【免费下载链接】obsidian-excel 项目地址: https://gitcode.com/gh_mirrors/ob/obsidian-excel 还在为Obsidian中简陋的Markdown表格而头疼吗&#xff1f;每次处理复杂数据都要在Excel和Obsi…...

避开这3个坑!用SARscape处理L波段数据时的实战经验总结

避开这3个坑&#xff01;用SARscape处理L波段数据时的实战经验总结 在植被监测和地表穿透分析领域&#xff0c;L波段雷达数据因其独特的物理特性成为不可替代的工具。与C波段相比&#xff0c;23cm的波长赋予它更强的穿透能力&#xff0c;能够穿透植被冠层获取下层结构信息&…...

GPT-5架构泄露?Kubernetes 1.31发布与Rust重构浪潮下的云原生之变

&#x1f525;个人主页&#xff1a;北极的代码&#xff08;欢迎来访&#xff09; &#x1f3ac;作者简介&#xff1a;java后端学习者 ❄️个人专栏&#xff1a;苍穹外卖日记&#xff0c;SSM框架深入&#xff0c;JavaWeb ✨命运的结局尽可永在&#xff0c;不屈的挑战却不可须臾或…...

Fish Speech 1.5行业方案:文旅景区多语种智能导览语音生成实践

Fish Speech 1.5行业方案&#xff1a;文旅景区多语种智能导览语音生成实践 1. 项目背景与需求分析 文旅景区面临着多语种导览的普遍痛点。传统人工录制多语言导览语音成本高昂&#xff0c;一个小型景区需要中英日韩四种语言的导览&#xff0c;仅录制费用就可能达到数万元。而…...

紧急预警:2024年Q3起,Llama-3-Vision、Qwen-VL等主流开源多模态模型在边缘设备运行时功耗超标率达68%——3套轻量化迁移方案限时公开

第一章&#xff1a;多模态大模型能耗优化策略 2026奇点智能技术大会(https://ml-summit.org) 多模态大模型&#xff08;如Flamingo、KOSMOS-2、Qwen-VL&#xff09;在图像理解、跨模态推理等任务中展现出强大能力&#xff0c;但其训练与推理阶段的能源消耗显著高于单模态模型…...

Java团队必看:为何转型AI应用开发已刻不容缓?

在数字化浪潮席卷全球的今天&#xff0c;AI技术正以前所未有的速度重塑各行各业。对于长期深耕Java领域的技术团队而言&#xff0c;转型AI应用开发不仅是顺应时代潮流的选择&#xff0c;更是保障技术竞争力、满足业务需求的必然之举。本文将从技术趋势、业务需求、开发效率三个…...

新手必看:用火眼取证工具搞定手机APP数据提取,从一道竞赛题讲起

火眼取证实战&#xff1a;从手机APP数据提取到OCR技术深度解析 取证工具在网络安全和电子数据调查中扮演着越来越重要的角色。作为一名长期从事电子取证工作的技术顾问&#xff0c;我经常遇到新手调查员在面对海量手机数据时感到无从下手。今天&#xff0c;我们就以火眼取证工具…...

nnUNetV2自定义网络实战:手把手教你修改PlainConvUNet,打造专属医学影像分割模型

nnUNetV2自定义网络实战&#xff1a;手把手教你修改PlainConvUNet&#xff0c;打造专属医学影像分割模型 医学影像分割领域&#xff0c;nnUNetV2凭借其出色的性能和易用性成为研究者的首选工具。但面对特殊病灶或罕见组织类型时&#xff0c;默认网络架构可能无法满足需求。本文…...