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

数组深入学习感悟

注:本文学习借鉴于《代码随想录》

一.介绍数组

数组是储存在连续内存空间中的相同类型数据的集合

数组名的理解:

数组名就是数组⾸元素(第⼀个元素)的地址是对的,但是有两个例外:
sizeof(数组名),sizeof中单独放数组名,这⾥的数组名表⽰整个数组,计算的是整个数组的⼤⼩,
单位是字节
&数组名,这⾥的数组名表⽰整个数组,取出的是整个数组的地址(整个数组的地址和数组⾸元素
的地址是有区别的)
除此之外,任何地⽅使⽤数组名,数组名都表⽰⾸元素的地址
数组中的元素不能删除,只能覆盖。

二.数组解题法

下面我们介绍数组解决问题的几大方法。

1.二分查找

适用类型:对于数组中在范围查找元素的位置,求解平方根,以及插入元素等。

使用前提:二分查找使用前一定要观察元素是否已排好位置

二分查找主要有以下两种写法:

1.1.左闭右闭[left,right]

该写法注意点:(本文不再进行基础实现讲解,可以翻看我的之前文章,有实现过程)
1.while (left <= right) 要使⽤ <= ,因为 left == right 是有意义的,所以使⽤ <=
2.if (nums[middle] > target) right 要赋值为 middle - 1 ,因为当前这个 nums[middle] ⼀定不是 target ,那么接下来要查找的左区间结束下标位置就是 middle - 1

对于leedcode这题:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

就是典型的第一类写法

下面是我对于该题的C语言解法代码:

int search(int* nums, int numsSize, int target) 
{int left=0;int right=numsSize-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{return mid;}}return -1;
}
时间复杂度: O(log n)
空间复杂度: O(1)

1.2.左闭右开[left,right)

注意点:

1.while (left < right) ,这⾥使⽤ < , 因为 left == right 在区间 [left, right) 是没有意义的
2.if (nums[middle] > target) right 更新为 middle ,因为当前 nums[middle] 不等于 target ,去左区间继续寻找,⽽寻找区间是左闭右开区间,所以right 更新为 middle ,即:下⼀个查询区间不会去⽐较 nums[middle]。
还是刚才那题,现在我们用第二种方法实现它:
int search(int* nums, int numsSize, int target) 
{int left=0;int right=numsSize;//注意right现在是被赋值为numsSizewhile(left<right){int mid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid;//由于用边界为空,所以right=mid,而不是right=mid-1}else{return mid;}}return -1;
}

补充:如果你想问有没有左开右闭的二分查找,我想说的是有,当使用的意义不大,所以作者这里就不讲了。

下面是推荐的练习题:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台   (69.x 的平⽅根)

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台        (367.有效的完全平⽅数)

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台           (35.搜索插⼊位置)
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台        (34.在排序数组中查找元素的第⼀个和最后⼀个位置)

这些题可能对你有点难,请加油,我相信你一定可以的。

2.双指针法(重点)

解释:双指针法是定义两个有关联的变量,可能是指针,也可能是整数,通过他们实现对数组的操作,使得高效,快捷。

具体的我们来在题目中去感受吧!

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

对于leedcod这题,大家第一反应可能就是暴力出手,疯狂遍历数组,一个for循环不行,那我两个,再不行,再加,但是现在来看看大佬们的思路,让你直呼666……
双指针法就是这题的良方妙药,下面我带着大家用双指针来实现它
由于是数组,我们定义两个整型变量,即slow和fast,表示快慢指针
快指针:寻找新数组的元素 ,新数组就是不含有⽬标元素的数组
慢指针:指向更新新数组下标的位置
看代码:
int removeElement(int* nums, int numsSize, int val) 
{//双指针法int src=0;int dest=0;while(src<numsSize){if(nums[src]!=val){nums[dest++]=nums[src++];}else{src++;}}return dest;
}

是不是大呼学到了。

关于双指针的使用场景,大家需要多做题,自己把握,这样慢慢可能就能感受的啥题目是考察双指针了。

来再带着大家看一题:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

对于这题,我们就直接开始双指针吧!

这题比较特殊,它是有序的,又是问平方,只需要比较负数的平方与整数平方关系即可,大家想想,如果我们定义两个指针,一个指向头,一个指向尾,是不是就可以最快的进行排好序。

看代码实现

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* sortedSquares(int* nums, int numsSize, int* returnSize) 
{*returnSize = numsSize;int* arr=(int*)malloc(numsSize*sizeof(int));int n=0;int m=numsSize-1;int c=numsSize-1;while(n<=m){int i=nums[n]*nums[n];int j=nums[m]*nums[m];if(i>j){arr[c--]=i;n++;}else//j>=i{arr[c--]=j;m--;}}return arr;
}
双指针⻛骚起来,也是⽆敌(转自程序员Carl)
下面给大家推荐几道好题:(不用说谢了,这种好东西,一定要拿出来共享,当时快把我写吐了)
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

刷完绝对对于双指针有一定的使用感觉了。

3.滑动窗口

如果大家深入了解过数组,就一定听过数组恶魔---滑动窗口
对于滑动窗口,连leedcode上都是中等题起步
下面我们就一题进行了解:
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
滑动窗⼝, 就是不断的调节⼦序列的起始位置和终⽌位置,从⽽得出我们要想的结果
我们应该可以看出,如果我们纯暴力来解决这题,就是两个for循环,但是如果用滑动窗口,一个for循环即可,下面来看看实现过程:
⾸先要思考 如果⽤⼀个 for 循环,那么应该表示滑动窗⼝的起始位置,还是终⽌位置。 如果只⽤⼀个for 循环来表示 滑动窗⼝的起始位置,那么如何遍历剩下的终⽌位置? 此时难免再次陷⼊ 暴⼒解法的怪圈。 所以只⽤⼀个for 循环,那么这个循环的索引,⼀定是表示滑动窗⼝的终⽌位置。
在本题中实现滑动窗⼝,主要确定如下三点:
窗⼝内是什么?
如何移动窗⼝的起始位置?
如何移动窗⼝的结束位置?
窗⼝就是 满⾜其和 s 的⻓度最⼩的 连续 ⼦数组。
窗⼝的起始位置如何移动:如果当前窗⼝的值⼤于 s 了,窗⼝就要向前移动了(也就是该缩⼩了)。
窗⼝的结束位置如何移动:窗⼝的结束位置就是遍历数组的指针,也就是 for 循环⾥的索引.
看代码实现过程:
int minSubArrayLen(int target, int* nums, int numsSize) 
{int size=0;int result=INT_MAX;int left=0;int sum=0;for(int right=0;right<numsSize;right++){sum+=nums[right];while(sum>=target){size=right-left+1;result=result<=size?result:size;sum-=nums[left++];}}return result==INT_MAX?0:result;
}

时间复杂度直接从O(N*N)降到了O(N),可见这种方法的强大。

推荐大家去B站看代码随想录视频,可能理解更加深入。

下面给大家推荐题目吧:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
这两题是真的难啊!!!加油
最后,给小编点赞呗kiss!

相关文章:

数组深入学习感悟

注&#xff1a;本文学习借鉴于《代码随想录》 一.介绍数组 数组是储存在连续内存空间中的相同类型数据的集合 数组名的理解&#xff1a; 数组名就是数组⾸元素(第⼀个元素)的地址是对的&#xff0c;但是有两个例外&#xff1a; sizeof(数组名)&#xff0c;sizeof中单独放数…...

亚马逊云科技-如何缩容/减小您的AWS EC2根卷大小-简明教程

一、背景 Amazon EBS提供了块级存储卷以用于 EC2 实例&#xff0c;EBS具备弹性的特点&#xff0c;可以动态的增加容量、更改卷类型以及修改预配置的IOPS值。但是EBS不能动态的减少容量&#xff0c;在实际使用中&#xff0c;用户也许会存在此类场景&#xff1a; 在创建AWS EC2…...

[Java 基础] Java Stream

Java Stream 是 Java 8 引入的新特性之一&#xff0c;它提供了一种新的处理数据集合的方式。Stream 可以使我们更加方便地对集合进行处理和操作&#xff0c;同时还能提高代码的简洁性和可读性。 文章目录 什么是 Stream常见用法创建 Stream中间操作终端操作 总结 什么是 Stream…...

达芬奇18.6DaVinci ResolveStudio(Win/Mac)激活版

DaVinci Resolve Studio 18是一款业界领先的视频后期制作软件&#xff0c;它集成了剪辑、调色、视觉特效、动态图形和音频后期制作等功能&#xff0c;为用户提供了完整的创作解决方案。该软件不仅适用于电影、电视和网页内容的制作&#xff0c;还广泛应用于广告、纪录片和独立电…...

力扣题目学习笔记(OC + Swift)16. 最接近的三数之和

16. 最接近的三数之和 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数&#xff0c;使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 排序 双指针 思路同15. 三数之和 简单地使用三重循环枚举所有的三…...

基于STM32的DHT11温湿度传感器与LCD显示器的集成设计

在本文中&#xff0c;我们将详细介绍如何基于STM32微控制器实现DHT11温湿度传感器与LCD显示器的集成设计。我们将包括硬件连接、软件编程以及涉及的STM32库函数和相关知识。这个项目旨在帮助您理解如何使用STM32来读取DHT11温湿度传感器的数据&#xff0c;并将数据显示在LCD显示…...

解决浏览器自动将http跳转至https导致无法访问的问题

以下只针对Chrome浏览器 方法一&#xff1a; 1.地址栏中输入chrome://net-internals/#hsts。 2.在Delete domain中输入项目的域名&#xff0c;并Delete&#xff08;删除&#xff09;。 3.可以在Query domain测试是否删除成功。 HSTS全称&#xff1a;HTTP Strict Transport Se…...

小程序面试题 | 07.精选小程序面试题

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…...

深度学习的推理部分

深度学习的推理部分指的是已经训练好的深度学习模型应用于新数据&#xff08;通常是测试或实际应用数据&#xff09;以进行预测、分类、分割等任务的过程。在深度学习中&#xff0c;训练和推理是两个阶段&#xff1a; 训练阶段&#xff1a; 在这个阶段&#xff0c;深度学习模型…...

如何用 CleanMyMac 来保护 Mac 隐私

大家早上好&#xff0c;中午好&#xff0c;下午好&#xff0c;晚上好。 在我们使用MacBook上的自带浏览器-Safari&#xff08;或者一些其他浏览器&#xff09;进行网页浏览的时候&#xff0c;往往会留下一些痕迹。如果这些痕迹涉及一些敏感数据信息的话&#xff0c;那么我们肯…...

opencv入门到精通——鼠标事件和Trackbar控件的使用

目标 了解如何在OpenCV中处理鼠标事件 您将学习以下功能&#xff1a;cv.setMouseCallback() 了解将轨迹栏固定到OpenCV窗口 您将学习以下功能&#xff1a;cv.getTrackbarPos&#xff0c;cv.createTrackbar等。 简单演示 在这里&#xff0c;我们创建一个简单的应用程序&am…...

iOS 收集 SDK 内部 log

为 SDK 设置 log 等级&#xff0c;设置 RCIMClient 的 logLevel 为您期望的&#xff0c;可以在 SDK initWithAppkey 之后设置&#xff0c;比如希望只收集错误 log&#xff0c;那么可以设置为 RC_Log_Level_Error&#xff0c;如果想一般信息、警告信息&#xff0c;错误信息都收集…...

【CSS @property】CSS自定义属性说明与demo

CSS property property - CSS: Cascading Style Sheets | MDN At 规则 - CSS&#xff1a;层叠样式表 | MDN Custom properties (–*): CSS variables - CSS: Cascading Style Sheets | MDN CSS Houdini - Developer guides | MDN &#x1f4da; 什么是property? property CSS…...

【华为数据之道学习笔记】6-3数据服务分类与建设规范

数据服务是为了更好地满足用户的数据消费需求而产生的&#xff0c;因此数据消费方的差异是数据服务分类的最关键因素。具体包括两大类&#xff1a;数据集服务和数据API服务。 1. 数据集服务 &#xff08;1&#xff09;数据集服务定义 比较常见的数据消费者有两类&#xff1a;一…...

Vue的脚手架

脚手架配置 脚手架文档&#xff1a;Vue CLI npm config set registry https://registry.npm.taobao.org vue.config.js配置选项&#xff1a; 配置参考 | Vue CLI ref选项 ref和id类似&#xff0c;给标签打标识。 document.getElementById(btn); this.$ref.btn; 父子组…...

Java实现Word中插入上标和下标

Java实现Word中插入上标和下标 Java不能直接在Word中插入上标和下标&#xff0c;但是可以通过POI库来实现。 下面提供一个Java代码示例&#xff0c;使用POI库向Word中插入带有上标和下标的文字&#xff1a; import org.apache.poi.xwpf.usermodel.XWPFDocument; import org.…...

Java和Python中的目标堆栈规划实现

目标堆栈规划是一种简单高效的人工智能规划算法&#xff0c;用于解决复合目标问题。它的工作原理是**将总体目标分解为更小的子目标&#xff0c;然后以向后的顺序逐一解决它们。 让我们考虑一个简单的例子来说明目标堆栈规划。想象一下你想要烤一个蛋糕&#xff0c;目标是准备…...

(前端)后管系统登录后隐藏url上信息同时获取url上携带参数~开发需求(bug)总结7

问题描述&#xff1a; 首先我这个后管项目是若依权限管理系统&#xff0c;路由实现都是动态加载的。现在有一个需求&#xff0c;后端会邮件发送系统中的链接&#xff0c;这个链接是携带参数(id、用户的加密信息)&#xff0c;比如&#xff1a;https://47.23.12.1/task/list?id…...

CSS3新增样式

1&#xff0c;圆角边框 在CSS3中&#xff0c;新增了圆角边框样式&#xff0c;这样我们的盒子就可以变圆角了 border-radious属性用于设置元素的外边框圆角 语法&#xff1a; border-radious&#xff1a;length&#xff1b; radious 半径&#xff08;圆的半径&#xff09;原理…...

HP服务器idrac设置以及系统安装

HP服务器idrac设置以及系统安装 一、设置管理口的地址和密码1、HP服务器重新界面选择"F9"进入BIOS&#xff0c;设置iLo5(idrac)的IP和用户名密码。2、选择"系统配置"。3、选择"iLO 4"配置程序。4、网络选项是设置idrac管理口的地址&#xff0c;设…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

中南大学无人机智能体的全面评估!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.…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...

写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里

写一个shell脚本&#xff0c;把局域网内&#xff0c;把能ping通的IP和不能ping通的IP分类&#xff0c;并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...

Three.js进阶之粒子系统(一)

一些特定模糊现象&#xff0c;经常使用粒子系统模拟&#xff0c;如火焰、爆炸等。Three.js提供了多种粒子系统&#xff0c;下面介绍粒子系统 一、Sprite粒子系统 使用场景&#xff1a;下雨、下雪、烟花 ce使用代码&#xff1a; var materialnew THRESS.SpriteMaterial();//…...

Pycharm的终端无法使用Anaconda命令行问题详细解决教程

很多初学者在Windows系统上安装了Anaconda后&#xff0c;在PyCharm终端中运行Conda命令时&#xff0c;会遇到以下错误&#xff1a; conda : 无法将“conda”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。 请检查名称的拼写&#xff0c;如果包括路径&#xff0c;请确保…...