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

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

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

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

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

[C++错误经验]case语句跳过变量初始化

标题&#xff1a;[C错误经验]case语句跳过变量初始化 水墨不写bug 文章目录 一、错误信息复现二、错误分析三、解决方法 一、错误信息复现 write.cc:80:14: error: jump to case label80 | case 2:| ^ write.cc:76:20: note: crosses initialization…...