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

算法打卡day1|数组篇|Leetcode 704.二分查找、27.移除元素

数组理论基础

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

1.数组下标都是从0开始的。

2.数组内存空间的地址是连续的。

正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址所以数组的元素是不能删的,只能覆盖。

在C++中二维数组在内存的空间地址是连续,但在java中并不是连续的。

java中的数组排列方式如下,所以Java的二维数组在内存中不是 3*4 的连续地址空间,而是四条连续的地址空间组成!

算法题

Leetcode 704.二分查找

题目链接:二分查找

大佬视频讲解:手把手带你撕出正确的二分法

个人思路

题目要求是用二分法;那具体步骤为:找到数组中间的值,将这个值循环与目标值对比,1.若找到目标值放回下标2.没找到目标值的话,则按照与目标值对比的大小,重新选择范围,再选择这个范围中的中间值继续对比;但这其中比较难解决的是范围的确定

解法

这道题目的前提是数组为有序数组,同时题目还强调数组中无重复元素,因此以后遇到此种类型都可以考虑使用二分法;

二分法中,对区间的定义很重要。区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

二分法第一种写法:左闭右闭

即[left, right];左闭右闭要注意以下两点

  1. 循环while中的判断条件 “(left <= right) ”要使用 <= ,因为left == right是有意义的。
  2. 目标值小于中间值,右区间需要改变时;right 要赋值为 mid - 1,因为当前这个nums[middle]一定不是target。
class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length-1;//定义target在左闭右闭的区间里,[left, right]if(target <nums[0]||target>nums[right-1]){//避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算return -1;}while(left<=right){int mid=left+((right-left)>>1);//防止溢出;>> 是右移位运算符,相当于除以 2 并向下取整if(nums[mid]==target){return mid;}else if(nums[mid]<target){//target 在右区间,即[mid + 1, right]left=mid+1;}else if(nums[mid]>target){//target 在左区间,即[left, mid- 1]right=mid-1;}}return -1;}
}

时间复杂度:O(log n);(折半循环)

空间复杂度:O(1);(没有使用多余空间)

二分法第二种写法:左闭右开

即[left, right);左闭右开要注意以下两点

  1. 循环while中的判断条件“(left < right)”,这里使用 < ,因为left == right在区间[left, right)是没有意义的
  2. 目标值小于中间值,右区间需要改变时, right 更新为 mid,因为下一个查询区间不会去比较nums[middle]
class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length;//定义target在左闭右开的区间里,[left, right]if(target <nums[0]||target>nums[right-1]){//避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算return -1;}while(left<right){int mid=left+((right-left)>>1);//防止溢出;>> 是右移位运算符,相当于除以 2 并向下取整if(nums[mid]==target){return mid;}else if(nums[mid]<target){//target 在右区间,即[mid + 1, right)left=mid+1;}else if(nums[mid]>target){//target 在左区间,即[left, mid)right=mid;}}return -1;}
}

时间复杂度:O(log n);(折半循环)

空间复杂度:O(1);(没有使用多余空间)

Leetcode27.移除元素

题目链接:27.移除元素

大佬视频讲解:数组中移除元素并不容易

个人思路

因为数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖,所以若要暴力解决的话,得两次循环,一次循环找与目标值对应的,二次循环将删除元素其后面的元素向前赋值;

这种解法慢,也可以换成双指针来解决,指针分为快慢指针,快指针找需要删除的元素,慢指针找新数组的下标;

解法
暴力解法

双重循环

class Solution {public int removeElement(int[] nums, int val) {int len= nums.length;for (int i = 0; i < len; i++) {if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位for (int j = i + 1; j < len; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位len--; // 此时数组的大小-1}}return len;}
}

时间复杂度:O(n^2);(两个for循环 n*n)

空间复杂度:O(1);(没有使用多余空间)

快慢双指针

搞清楚双指针的定义非常关键,快指针的作用是寻找新数组的元素 ,新数组就是不含有目标元素的数组;慢指针的作用是指向更新 新数组下标的位置

class Solution {public int removeElement(int[] nums, int val) {int slow=0;//慢指针for(int fast=0;fast<nums.length;fast++){if(nums[fast]!=val){//如果没有找到目标元素则一起向前遍历nums[slow]=nums[fast];slow++;}}return slow;}
}

时间复杂度:O( n);(一个for循环)

空间复杂度:O(1);(没有使用多余空间)

以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

相关文章:

算法打卡day1|数组篇|Leetcode 704.二分查找、27.移除元素

数组理论基础 数组是存放在连续内存空间上的相同类型数据的集合&#xff0c;可以方便的通过下标索引的方式获取到下标下对应的数据。 1.数组下标都是从0开始的。 2.数组内存空间的地址是连续的。 正是因为数组的在内存空间的地址是连续的&#xff0c;所以我们在删除或者增添…...

什么是高阶组件

高阶组件&#xff08;HOC&#xff09;是 React 中用于复用组件逻辑的一种高级技巧。简单来说&#xff0c;高阶组件就是一个函数&#xff0c;该函数接受一个组件作为参数&#xff0c;并返回一个新的组件。这个新的组件会使用你传给它的组件作为子组件。 高阶组件并不是真的组件…...

python实现裂区试验方差分析

方差分析&#xff08;Analysis of Variance&#xff0c;ANOVA&#xff09;是一种统计方法&#xff0c;用于比较三个或三个以上组别的平均值是否存在显著差异。它通过比较组内变异和组间变异的大小来判断组别间的平均值是否有显著差异。 方差分析通常用于以下情况&#xff1a; …...

Vue v-for、v-if、v-show常见问题

vue使用v-for遍历对象时&#xff0c;是按照什么顺序遍历的&#xff1f;如何保证顺序&#xff1f; 会先判断对象是否存在iterator接口&#xff0c;如果有循环执行next()方法。 没有iterator的情况下&#xff0c;会调用Object.Keys()方法&#xff0c;在不同的浏览器中&#xff…...

GPT技术在学术研究中的革命性应用:开启论文创作新篇章

在学术界&#xff0c;撰写高质量的论文一直是一个挑战性的任务&#xff0c;它不仅需要深厚的专业知识&#xff0c;还要求良好的文献综述能力、数据分析技巧以及清晰的表达能力。近年来&#xff0c;随着人工智能技术的飞速发展&#xff0c;尤其是生成式预训练变换器&#xff08;…...

【K8s】-- 描述容器中 pod 的状态

命令&#xff1a;kubectl describe pod -n 你的namespace名称 pod 名称 举例&#xff1a;kubectl describe pod -n my-flink --context prod-5 test-record-all-new-mc-taskmanager-1-1 Name: test-record-all-new-mc-taskmanager-1-1 Namespace: ky-flink Pri…...

使用yolo-seg模型实现自定义自动动态抠图

yolov8导航 如果大家想要了解关于yolov8的其他任务和相关内容可以点击这个链接&#xff0c;我这边整理了许多其他任务的说明博文&#xff0c;后续也会持续更新&#xff0c;包括yolov8模型优化、sam等等的相关内容。 YOLOv8&#xff08;附带各种任务详细说明链接&#xff09; …...

FairyGUI × Cocos Creator 3.x 场景切换

前言 前文提要&#xff1a; FariyGUI Cocos Creator 入门 FairyGUI Cocos Creator 3.x 使用方式 个人demo&#xff1a;https://gitcode.net/qq_36286039/fgui_cocos_demo_dust 个人demo可能会更新其他代码&#xff0c;还请读者阅读本文内容&#xff0c;自行理解并实现。 官…...

【Java程序设计】【C00288】基于Springboot的篮球竞赛预约平台(有论文)

基于Springboot的篮球竞赛预约平台&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的篮球竞赛预约平台 本系统分为前台功能模块、管理员功能模块以及用户功能模块。 前台功能模块&#xff1a;用户进入到平台首页&a…...

textbox文本框跨线程写入,扩展textobx控件

在Windows Forms中&#xff0c;由于UI控件不是线程安全的&#xff0c;直接跨线程访问和修改UI控件通常会导致不可预测的行为或异常。TextBox 控件同样不能直接从非创建它的线程进行写入。为了安全地在不同线程间更新 TextBox 控件的内容&#xff0c;你可以使用控件的 Invoke 方…...

【踩坑】PyTorch中指定GPU不生效和GPU编号不一致问题

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] 指定GPU不生效问题 解释&#xff1a;就是使用os.environ["CUDA_VISIBLE_DEVICES"] "1"后&#xff0c;后面使用起来仍然是cuda0. 解决&#xff1a;在最开头就使用 import os os.environ[&…...

线性代数:向量、张量、矩阵和标量

线性代数&#xff1a;向量、张量、矩阵和标量 背景 在线性代数中&#xff0c;向量、张量、矩阵和标量都属于基础概念&#xff0c;特别是最近AI的爆火&#xff0c;向量和张量的概念也越来越普及&#xff0c;本文将介绍下这些基本概念。 1. 标量&#xff08;Scalar&#xff0…...

WordPres Bricks Builder 前台RCE漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…...

渗透测试—信息收集

渗透测试—信息收集 1. 收集域名信息1.1. 域名注册信息1.2. SEO信息收集1.3. 子域名收集1.3.1. 在线子域名收集1.3.2. 子域名收集工具 1.4. 域名备案信息1.5. ICP备案号查询1.6. SSL证书查询 2. 收集真实IP2.1. 超级ping2.2. Ping2.3. CDN绕过 3. 收集旁站或C段IP3.1. 旁站或C段…...

安卓adb调试备忘录

由于 MAC 的 USB 口全被占用着&#xff0c;采用无线连接刚方便&#xff0c;记录一下&#xff0c;以防忘记~ ADB原理 adb devices -l ## 列出连接的设备adb tcpip [端口号] adb tcpip 6666 # 将当前已连接USB上的Mobile端切换为TCP/IP模式&#xff0c;以6666端口进行监听. adb…...

【软件架构】01-架构的概述

1、定义 软件架构就是软件的顶层结构 RUP&#xff08;统一过程开发&#xff09;4 1 视图 1&#xff09;逻辑视图&#xff1a; 描述系统的功能、组件和它们之间的关系。它主要关注系统的静态结构&#xff0c;包括类、接口、包、模块等&#xff0c;并用于表示系统的组织结构…...

Vue 图片轮播第三方库 介绍

Vue图片轮播是一种在网页上以自动或手动方式展示图片的组件&#xff0c;常用于产品展示、网站banner等场景。有许多第三方库可以帮助Vue开发者轻松实现图片轮播功能。以下是一些流行的Vue图片轮播第三方库的介绍&#xff1a; 1. Vue-awesome-swiper - **简介**&#xff1a;V…...

设置主从复制时发生报错Could not find first log file name in binary log index file‘;解决方案

如图所示&#xff0c;slave_io_runnind:no,slave_sql_running:yes 此时&#xff0c;主从配置错误&#xff0c;我们可以查看Last_IO_Error:来查看报错信息 此时&#xff0c;我们需要停止从服务器的主从服务&#xff0c; mysql> stop slave; Query OK, 0 rows affected, 1 w…...

React Context的使用方法

背景&#xff1a;在某些场景下&#xff0c;你想在整个组件树中传递数据&#xff0c;但却不想手动地在每一层传递属性&#xff0c;你可以直接在React中使用强大的contextAPI 解决上述问题 在一个典型的React 中&#xff0c;数据通过Props属性自下而上&#xff08;由父及子&…...

ElasticSearch索引数据备份与恢复

索引数据备份 在磁盘创建备份目录并授权 # 创建备份目录 /home/esbackup # 授权 chmod 777 /home/esbackup修改配置文件elasticsearch.yml echo path.repo: ["/home/esbackup"] >> /etc/elasticsearch/elasticsearch.yml重启elasticsearch(我是docker创建的…...

HarmonyOS开发入门:DevEco Studio工程目录结构详解与实战配置

HarmonyOS开发实战&#xff1a;深度解析DevEco Studio工程架构与高效配置策略 当你第一次在DevEco Studio中创建HarmonyOS项目时&#xff0c;是否曾被复杂的目录结构弄得一头雾水&#xff1f;作为华为全场景智能生态的核心开发工具&#xff0c;DevEco Studio采用了一套精心设计…...

模型航空喷气发动机CAD全套图纸(32张)

模型航空喷气发动机CAD学习资料是一套针对航空模型动力系统设计的系统性资源&#xff0c;涵盖从整体结构到局部零件的详细设计思路。32张图纸以标准化工程语言呈现&#xff0c;包含发动机外壳、燃烧室、涡轮组件、进气导管等核心模块的二维与三维视图&#xff0c;通过精确的线条…...

多策略融合改进蜣螂算法:Fuch混沌初始化与自适应变异优化MATLAB实现

1. 蜣螂算法基础与改进需求 蜣螂优化算法&#xff08;Dung Beetle Optimizer, DBO&#xff09;是受自然界蜣螂行为启发而设计的一种新型群体智能算法。它通过模拟蜣螂的滚球、繁殖、觅食和偷窃四种核心行为&#xff0c;实现了对解空间的高效探索。但在处理高维复杂函数优化问题…...

大麦抢票自动化工具:3分钟提升10倍成功率的技术秘籍

大麦抢票自动化工具&#xff1a;3分钟提升10倍成功率的技术秘籍 【免费下载链接】ticket-purchase 大麦自动抢票&#xff0c;支持人员、城市、日期场次、价格选择 项目地址: https://gitcode.com/GitHub_Trending/ti/ticket-purchase 你是否经历过这样的场景&#xff1f…...

硬件编译器工具链新手指南:从概念到实践

硬件编译器工具链新手指南&#xff1a;从概念到实践 【免费下载链接】circt Circuit IR Compilers and Tools 项目地址: https://gitcode.com/gh_mirrors/ci/circt 一、CIRCT核心价值解析 在硬件设计领域&#xff0c;你是否曾面临这些挑战&#xff1a;高级算法难以直接…...

别再被NFS的‘非法端口’拦住了!手把手教你用insecure选项解决mount.nfs: access denied

突破NFS端口限制&#xff1a;深入解析insecure选项的实战应用 上周在调试一个嵌入式开发环境时&#xff0c;遇到了一个典型的NFS挂载问题。当我在VirtualBox虚拟机中尝试挂载物理机上的NFS共享目录时&#xff0c;终端突然弹出mount.nfs: access denied by server while mountin…...

Windows持久化核心战术:系统服务植入实战教程

前言技术背景&#xff1a;在网络攻击的生命周期&#xff08;Cyber Kill Chain&#xff09;中&#xff0c;持久化&#xff08;Persistence&#xff09; 是攻击者在失陷主机上维持长期访问权限的关键阶段。在众多持久化技术中&#xff0c;将恶意程序注册为系统服务&#xff08;Sy…...

淘宝淘金币自动化脚本:每天节省20分钟的终极解决方案

淘宝淘金币自动化脚本&#xff1a;每天节省20分钟的终极解决方案 【免费下载链接】taojinbi 淘宝淘金币自动执行脚本&#xff0c;包含蚂蚁森林收取能量&#xff0c;芭芭农场全任务&#xff0c;解放你的双手 项目地址: https://gitcode.com/gh_mirrors/ta/taojinbi 淘宝淘…...

突破性全流程AI科研助手:AI-Scientist-v2重塑科学探索范式

突破性全流程AI科研助手&#xff1a;AI-Scientist-v2重塑科学探索范式 【免费下载链接】AI-Scientist-v2 The AI Scientist-v2: Workshop-Level Automated Scientific Discovery via Agentic Tree Search 项目地址: https://gitcode.com/GitHub_Trending/ai/AI-Scientist-v2 …...

Jaspersoft Studio 动态字体颜色设置实战指南

1. 为什么需要动态字体颜色&#xff1f; 在报表开发中&#xff0c;数据可视化是提升信息传达效率的关键手段。想象一下&#xff0c;当你的老板查看月度销售报表时&#xff0c;如果所有数字都是千篇一律的黑色&#xff0c;他需要花费多少时间才能找到异常数据&#xff1f;而如果…...