【代码随想录】算法训练营 第一天 第一章 数组 Part 1
目录
数组基础知识补充
704. 二分查找
题目
左闭右闭方法
思路
代码
左闭右开方法
思路
代码
27. 移除元素
题目
暴力解法
思路
代码
双指针法
思路
代码
数组基础知识补充
1. 在leecode中,数组一般是以vector容器的形式出现的,虽然vector的底层实现是array,但严格来讲vector是容器,不是数组;
2. 数组元素的删除和增添都需要移动后续元素,而且在实现的角度上看,数组元素是不能删的,只能用后一个元素将其覆盖掉,然后再逐个覆盖,就相当于向前移动后续元素了;
3. C++二维数组的存储空间是连续的,但Java的不是,Java中每一个外层数组都会有指针指向内层数组的地址。
704. 二分查找
题目


左闭右闭方法
左闭右闭,意味着搜索区间是闭合的,比如 [ 1 , 5 ],在这种区间搜索元素,两个指针指向同一个元素时一定是有意义的,因为区间涉及到的元素都在区间内;
但如果搜索区间是半开半闭的,那么就要考虑指针不能指向开的那个元素,需要对代码进行一定的改动。
思路
用二分查找来做这道题是高效且简单的,因为元素递增不重复;
闭合区间二分的思路是,分别给数组的最左边和最右边一个指针,每次通过求两个指针指向地址的中间处那个元素的值,来判断是否和目标值相等,相等的话就返回中间处的值的下标,不相等的话则分为两种情况:
如果中间处的值小于目标值,以为这中间处以及它的左边的元素都太小,所以接下来我们就把搜索区间的左边界缩到中间处右边一个的元素那里;
如果中间处的值大于目标值,同理就把搜索区间的右边界缩小到中间处左边一个的元素那里。
因为这里是一个闭区间,所以二分的终止条件就是两个指针指向相同,这时候如果指向的元素不等于目标值,那就返回 -1 。
代码
class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1; int mid = 0;while (l <= r) {mid = l + (r - l) / 2; // 防止l和r过大,直接相加越界if (nums[mid] == target)return mid;if (nums[mid] < target)l = mid + 1;elser = mid - 1;}// 带入一个有两个元素的数组测试样例就知道,如果我们的目标是后者,第一次的mid指向前面那个,后面的l加一以后就指向目标了,这时候l和r相等,mid也和它们相等了,可以得到结论;//如果没有在while条件中写=,那么l和r指向相同时就直接跳出循环了,这时候mid还未赋新值,就会出错return -1;}
};
左闭右开方法
思路
大体上和上面的方法一样,主要注意的是while的终止条件,这时候就不能是指针指向相同了,要把等于号去掉,因为区间边界一开一闭,两者显然是不能混为一谈的;
另外,开区间的那一边的搜索边界需要注意,如果mid指向的元素大于目标值,那么这时候将有边界缩小到mid即可,不用减一,具体见代码。
代码
class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size();while (l < r) {int mid = l + (r - l) / 2;if (nums[mid] < target)l = mid + 1;else if (nums[mid] > target)r = mid; // 这时候不能再写mid-1了,因为这是开区间,mid肯定不可能是目标值了,但是mid-1可能是,如果把mid-1赋值给r,那就意味着排除掉了mid-1elsereturn mid;}return -1;}
};
27. 移除元素
题目
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
暴力解法
思路
用内外两层指针,外层指针遍历数组并寻找和目标值相等的元素,找到以后使用内层指针遍历该元素之后的所有元素,将所有元素往前移动一位,其实就是用后一个元素将前一个元素覆盖掉;
其中有一些细节需要注意,首先是数组长度要实时记录,最后返回的就是数组长度,而且每次覆盖一轮后数组长度就减一了,所以外层指针相应地也要减一。
代码
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) {for (int j = i + 1; j < size; j++)nums[j - 1] = nums[j];i--;size--;} }return size;}
};
双指针法
思路
使用一快一慢两个指针,用一个for循环完成两个for循环的任务。
首先定义一个慢指针,在此基础上再定义一个快指针在数组里从头扫到尾,如果遇见不等于目标值的数,就把这个数赋值给慢指针,相当于用慢指针创造了一个不包含目标值的新数组,但是这个新数组使用的就是原数组的空间。
代码
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0;for (int fast = 0; fast < nums.size(); fast++) {if (nums[fast] != val)nums[slow++] = nums[fast];}return slow; // 因为最后slow还有一个++,所以这里直接返回,不用+1}
};
相关文章:
【代码随想录】算法训练营 第一天 第一章 数组 Part 1
目录 数组基础知识补充 704. 二分查找 题目 左闭右闭方法 思路 代码 左闭右开方法 思路 代码 27. 移除元素 题目 暴力解法 思路 代码 双指针法 思路 代码 数组基础知识补充 1. 在leecode中,数组一般是以vector容器的形式出现的,虽然ve…...
286_C++_定时器的其中一个操作,定时重载接口—startTimer循环执行回调(未完全)
1、启动一个定时器,允许在一定时间间隔内执行回调函数startTimer 1、接口函数参数详解 /*** @brief startTimer 定时重载接口* @param interval 定时器触发间隔,单位毫秒 (ms)* @param notify 定时时间到后需要触发的回调* @param type 回调驱动方…...
自动驾驶学习笔记(四)——变道绕行仿真
#Apollo开发者# 学习课程的传送门如下,当您也准备学习自动驾驶时,可以和我一同前往: 《自动驾驶新人之旅》免费课程—> 传送门 《2023星火培训【感知专项营】》免费课程—>传送门 文章目录 前言 仿真内容 启动Dreamview 开启Sim…...
C++位图,布隆过滤器
本期我们来学习位图,布隆过滤器等相关知识,以及模拟实现,需求前置知识 C-哈希Hash-CSDN博客 C-封装unordered_KLZUQ的博客-CSDN博客 目录 位图 布隆过滤器 海量数据面试题 全部代码 位图 我们先来看一道面试题 给 40 亿个不重复的无符号…...
Python多种方法实现九九乘法表
你好,我是悦创。 九九乘法表是一种常见的算术学习工具,通常用于帮助学生记住乘法的基本运算。以下是使用Python实现九九乘法表的几种方法: 1. 使用两个嵌套循环 for i in range(1, 10):for j in range(1, i 1):print(f"{j}x{i}{i * …...
【力扣1876】长度为三且各字符不同的子字符串
👑专栏内容:力扣刷题⛪个人主页:子夜的星的主页💕座右铭:前路未远,步履不停 目录 一、题目描述二、题目分析 一、题目描述 题目链接:长度为三且各字符不同的子字符串 如果一个字符串不含有任何…...
HSN:微调预训练ViT用于目标检测和语义分割,华南理工和阿里巴巴联合提出
今天跟大家分享华南理工大学和阿里巴巴联合提出的将ViT模型用于下游任务的高效微调方法HSN,该方法在迁移学习、目标检测、实例分割、语义分割等多个下游任务中表现优秀,性能接近甚至在某些任务上超越全参数微调。 论文标题:Hierarchical Side…...
机器学习的原理是什么?
训过小狗没? 没训过的话总见过吧? 你要能理解怎么训狗,就能非常轻易的理解机器学习的原理. 比如你想教小狗学习动作“坐下”一开始小狗根本不知道你在说什么。但是如果你每次都说坐下”然后帮助它坐下,并给它一块小零食作为奖励,经过多次…...
Java集合框架之ArrayList源码分析
文章目录 简介ArrayList底层数据结构初始化集合操作追加元素插入数据删除数据修改数据查找 扩容操作总结 简介 ArrayList是Java提供的线性集合,本篇笔记将从源码(java SE 17)的角度学习ArrayList: 什么是ArrayList?ArrayList底层数据结构是…...
TensorFlow入门(二十、损失函数)
损失函数 损失函数用真实值与预测值的距离指导模型的收敛方向,是网络学习质量的关键。不管是什么样的网络结构,如果使用的损失函数不正确,最终训练出的模型一定是不正确的。常见的两类损失函数为:①均值平方差②交叉熵 均值平方差 均值平方差(Mean Squared Error,MSE),也称&qu…...
MySQL中死锁
数据库的死锁是指不同的事务在获取资源时相互等待,导致无法继续执行的一种情况。当发生死锁时,数据库会自动中断其中一个事务,以解除死锁。在数据库中,事务可以分为读事务和写事务。读事务只需要获取读锁,而写事务需要…...
【LeetCode刷题(数据结构)】:给定一个链表 每个节点包含一个额外增加的随机指针 该指针可以指向链表中的任何节点或空节点 要求返回这个链表的深度拷贝
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next…...
uniapp封装loading 的动画动态加载
实现效果 html代码 <view class"loadBox" v-if"loading"><img :src"logo" class"logo"> </view> css代码 .loadBox {width: 180rpx;min-height: 180rpx;border-radius: 50%;display: flex;align-items: center;j…...
Kopler.gl笔记:可视化功能总览
1 添加数据 2 添加图层 打开“数据层”菜单,开始可视化。 层(Layers)简单来说就是可以相互叠加的数据可视化。 3 添加过滤器 在地图上添加过滤器以限制显示的数据。过滤器必须基于数据集中的列。要创建新的过滤器,打开“过滤器…...
rust学习Cell、RefCell、OnceCell
背景 Rust 内存安全基于以下规则:给定一个对象 T,它只能具有以下之一: 对对象有多个不可变引用 (&T)(也称为别名 aliasing)对对象有一个可变引用 (&mut T)(也称为可变性 mutability)这是由 Rust 编译器强制执行的。然而,在某些情况下,该规则不够灵活(this r…...
基于SSM的摄影约拍系统
基于SSM的摄影约拍系统的设计与实现 开发语言:Java数据库:MySQL技术:SpringSpringMVCMyBatisJSP工具:IDEA/Ecilpse、Navicat、Maven 【主要功能】 前台系统:首页拍摄作品展示、摄影师展示、模特展示、文章信息、交流论…...
分析智能平台VMware Greenplum 7 正式发布!
📢📢📢📣📣📣 哈喽!大家好,我是【IT邦德】,江湖人称jeames007,10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】!😜&am…...
动态规划算法(3)--0-1背包、石子合并、数字三角形
目录 一、0-1背包 1、概述 2、暴力枚举法 3、动态规划 二、石子合并问题 1、概述 2、动态规划 3、环形石子怎么办? 三、数字三角形问题 1、概述 2、递归 3、线性规划 四、租用游艇问题 一、0-1背包 1、概述 0-1背包:给定多种物品和一个固定…...
Linux C/C++ 嗅探数据包并显示流量统计信息
嗅探数据包并显示流量统计信息是网络分析中的一种重要技术,常用于网络故障诊断、网络安全监控等方面。具体来说,嗅探器是一种可以捕获网络上传输的数据包,并将其展示给分析人员的软件工具。在嗅探器中,使用pcap库是一种常见的方法…...
Vitis导入自制IP导致无法构建Platform
怎么还有这种问题( 解决Vitis导入自制IP导致无法构建Platform – TaterLi 个人博客 Vitis报错:fatal error: xxx.h: No such file or directory._ly2lj的博客-CSDN博客 在指定位置黏入以上代码即可: INCLUDEFILES$(wildcard *.h) LIBSOUR…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
