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

YOLOv12涨点改进| TGRS 2025 | 全网独家创新、涨点上采样改进篇| 引入LSE-FPN拉普拉斯增强特征金字塔,有效提升各层特征的表达,含A2C2f_LSE二次创新,小目标检测高效涨点

一、本文介绍 🔥本文给大家介绍利用 LSE-FPN拉普拉斯增强特征金字塔 改进YOLOv12网络模型, 通过在特征金字塔中加入局部语义增强机制并改进多尺度特征融合方式,有效提升了各层特征的表达能力。该模块能够强化低层特征的语义信息,使模型在小目标检测和复杂场景下表现更优,…...

3分钟突破百度网盘资源壁垒:智能链接解析工具革新资源获取体验

3分钟突破百度网盘资源壁垒&#xff1a;智能链接解析工具革新资源获取体验 【免费下载链接】baidupankey 项目地址: https://gitcode.com/gh_mirrors/ba/baidupankey 你是否经历过这样的场景&#xff1a;导师分享的学术资料被提取码挡在门外&#xff0c;加班急需的项目…...

构建智能体协作网络:从 MCP 资源连接到 A2A 通信的 Agentic AI 工程实践

1. 智能体协作网络的基础架构 想象一下&#xff0c;你正在指挥一支由不同专家组成的团队完成市场报告。数据分析师负责整理数据&#xff0c;文案专员负责撰写内容&#xff0c;而行政助理则负责最终分发。在AI领域&#xff0c;这样的分工协作正是通过MCP协议和A2A协议实现的。前…...

基于MATLAB RVC与Simulink的ABB-IRB-1200运动学建模及轨迹规划实战

1. ABB-IRB-1200机械臂与MATLAB RVC工具箱初探 第一次接触ABB-IRB-1200这款机械臂时&#xff0c;我就被它精巧的设计所吸引。这款机械臂有两种型号&#xff0c;工作范围分别是700mm和900mm&#xff0c;最大有效负载分别为7kg和5kg。别看它体积小&#xff0c;在狭小空间内作业时…...

【多模态实战】Swift框架高效微调Qwen2-VL:从SFT到RLHF的完整指南

1. 为什么选择Swift框架微调Qwen2-VL 第一次接触Qwen2-VL这个多模态大模型时&#xff0c;我被它强大的图文理解能力惊艳到了。但真正让我惊喜的是发现Swift框架能让模型微调变得如此简单。记得当时为了测试一个定制化需求&#xff0c;传统方法需要写上百行训练代码&#xff0c;…...

原神抽卡记录导出工具:一键备份分析你的抽卡历史数据

原神抽卡记录导出工具&#xff1a;一键备份分析你的抽卡历史数据 【免费下载链接】genshin-wish-export biuuu/genshin-wish-export - 一个使用Electron制作的原神祈愿记录导出工具&#xff0c;它可以通过读取游戏日志或代理模式获取访问游戏祈愿记录API所需的authKey。 项目…...

保姆级教程:在Ubuntu 22.04物理机上,从开启SSH到配置IPv6防火墙的完整流程

Ubuntu 22.04物理机从SSH配置到IPv6防火墙的完整安全指南 当你拿到一台全新的Ubuntu物理机时&#xff0c;如何安全地配置远程访问并启用IPv6连接&#xff1f;本文将带你从零开始&#xff0c;一步步完成从系统初始化到防火墙配置的全过程。无论你是搭建家庭服务器、开发测试环境…...

香橙派Ubuntu镜像烧录与系统迁移实战指南

1. 香橙派与Ubuntu镜像的完美组合 香橙派作为国产开源硬件中的佼佼者&#xff0c;凭借其出色的性价比和丰富的接口&#xff0c;已经成为很多开发者和创客的首选。而Ubuntu作为最受欢迎的Linux发行版之一&#xff0c;以其稳定性和易用性赢得了大量用户的青睐。将这两者结合起来&…...

低成本AI助手方案:OpenClaw+Qwen3-32B私有镜像替代GPT-4

低成本AI助手方案&#xff1a;OpenClawQwen3-32B私有镜像替代GPT-4 1. 为什么选择本地化AI助手 去年冬天&#xff0c;当我第37次收到OpenAI API的账单时&#xff0c;手指悬在支付按钮上迟迟按不下去——单月$127的支出已经超出了个人项目的预算红线。作为一个独立开发者&…...

python vue基于hadoop的高校图书馆借阅阅读书目智慧推荐系统

目录技术架构设计数据采集与存储模块数据处理与分析模块推荐算法实现Vue前端开发系统部署方案测试与优化项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作技术架构设计 系统采用前后端分离架构&#xff0c;前端使用Vue.js框架开…...