数组篇刷题总结

news/2024/4/24 21:42:58/

二分查找:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
 

提示:

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/binary-search
 

代码:

class Solution 
{
public:int search(vector<int>& nums, int target) {//闭区间[leftPos,rightPos]、[1,1]//    int leftPos = 0;//    int rightPos = nums.size() - 1;//    int mid;//     while(leftPos <= rightPos)//     {//         mid = (leftPos + rightPos) / 2;//         if(nums[mid] > target)//         {//             rightPos = mid - 1;//         }else if(nums[mid] < target)//         {//             leftPos = mid + 1;//         }else//         {//             return mid;//         }//     }//     return -1;// }int leftPos = 0;int rightPos = nums.size();int mid;while(leftPos < rightPos){mid = (leftPos + rightPos) / 2;if(nums[mid] > target){rightPos = mid;}else if(nums[mid] < target){leftPos = mid + 1;}else{return mid;}}return -1;}};

移除元素:

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
 

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
 

提示:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-element
 

代码:

class Solution 
{
public:int removeElement(vector<int>& nums, int val) {int fast;//快指针int slow = 0;//慢指针for(int fast = 0; fast < nums.size(); fast++){if(nums[fast] != val){nums[slow++] = nums[fast];}}return slow;}
};

有序数组的平方:

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例 1:

输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:

输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
 

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
 

进阶:

请你设计时间复杂度为 O(n) 的算法解决本问题

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/squares-of-a-sorted-array
 

代码:

class Solution 
{//双指针法
public:vector<int> sortedSquares(vector<int>& nums){int i = 0;int j = nums.size()  - 1;vector<int> array(nums.size(), 0);int k = array.size() - 1;while(i <= j){if(nums[i] * nums[i] > nums[j] * nums[j]){array[k] = nums[i] * nums[i];i++;k--;}else{array[k] = nums[j] * nums[j];j--;k--;}}return array;}
};

长度最小的子数组:

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:

输入:target = 4, nums = [1,4,4]
输出:1
示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
 

提示:

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-size-subarray-sum
 

代码:

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {int i = 0;int maxLength = INT32_MAX; //将它设置为最大长度int sum = 0;int count = 0;for(int j = 0; j < nums.size(); j++){sum += nums[j];while(sum >= target){count = j - i + 1;maxLength = maxLength < count ? maxLength : count;sum -= nums[i++];}}return maxLength == INT32_MAX ? 0 : maxLength;}
};

螺旋矩阵II:

给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1:


输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]
示例 2:

 

输入:n = 1
输出:[[1]]
 

提示:

1 <= n <= 20

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/spiral-matrix-ii

代码:

class Solution 
{
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n, 0)); // int startX = 0,startY = 0;int mid = n / 2; //最后奇数位置int offset = 1; //左闭右开int count = n / 2; //判断有几层int sum = 1;int i,j;while(count--){i = startY;j = startX;for(i = startY; i < n - offset; i++){res[startX][i] = sum++;}for(j = startX; j < n - offset; j++){res[j][i] = sum++;}for(;i > startY; i--){res[j][i] = sum++;}for(;j > startX; j--){res[j][i] = sum++;}startX++;startY++;offset++;}if(n % 2){res[mid][mid] = sum;}return res;}
};

http://www.ppmy.cn/news/47464.html

相关文章

win11下载配置Python环境+pycharm下载

前两天快乐的把我重装的win10升级成win11&#xff0c;升级的时候超怕不能成功&#xff0c;但效果还不错&#xff0c;然后突然想学一学Python&#xff0c;所以首先来配置环境吧 一、下载安装包 建议去官网&#xff0c;因为自从有了Python3之后&#xff0c;Python2就慢慢的被淘汰…

Difference between HTTP3 and HTTP2

HTTP3目前还在不断更新中。一般每个新版本的优化&#xff0c;都会主要针对上一个版本的缺点。 对HTTP2&#xff0c;有二进制编码、头部压缩、多路复用、服务器推送等新特性去弥补了HTTP1.1中的不足。不过HTTP2基于TCP实现的&#xff0c;带3个缺陷&#xff1a;① TCP层面的队头阻…

常见的注册中心Nacos、Eureka

常见的注册中心 1.Eureka&#xff08;原生&#xff0c;2.0遇到瓶颈&#xff0c;停止维护&#xff09; 2.Zookeeper&#xff08;支持&#xff0c;专业的独立产品。例如&#xff1a;dubbo&#xff09; 3.Consul&#xff08;原生&#xff0c;GO语言开发&#xff09; 4.Nacos …

Vue CLI 浏览器兼容性

Vue CLI 浏览器兼容性 browserslist 你会发现有 package.json 文件里的 browserslist 字段 (或一个单独的 .browserslistrc 文件)&#xff0c;指定了项目的目标浏览器的范围。这个值会被 babel/preset-env 和 Autoprefixer 用来确定需要转译的 JavaScript 特性和需要添加的 CS…

康耐视Designer,通过VC5与西门子S7-1200 PLCProfinet通讯详细

测试使用软件版本 Designer Version: 2.7 GSD: GSDML-V2.3-Cognex-VC5-20140828STEP 7 Professional V14Network Configurator Version: 3.56测试使用硬件 Cognex Vision Controller VC5CIC-5000Siemens PLC: S7-1200 CPU 1214C DC/DC/RLY1.PLC端设置 1.新建一个项目,添加对应…

WxGL应用实例:绘制高精度的3D太阳系模型

文章目录 1 坐标系的选择1.1 黄道坐标系1.2 三维空间直角坐标系 2 使用JPL星历表计算轨道2.1 日期时间2.2 特定时刻天体的位置2.3 天体运行轨道 3 太阳系模型3. 1 全家福3.2 时间、距离和半径的缩放3.3 黄道坐标系模型 天何所沓&#xff1f;十二焉分&#xff1f;日月安属&#…

做好Python工程师,首先你需要做好的几件事

做好Python工程师&#xff0c;需要做好的几件事&#xff0c;我想分享给大家。首先千万不要做事周折。在你提问之前&#xff0c;先好好想一想&#xff0c;这个问题自己能不能解决。如果能解决&#xff0c;尽量自己解决&#xff1b;如果解决不了&#xff0c;那就要把你的问题描述…

开发方案/红外线人体体温计方案

红外线人体测温仪&#xff0c;是一款非常不错的测温设备&#xff0c;他可以适用于多种场合&#xff0c;尤其是在疫情期间&#xff0c;很多场所都需要这种设备&#xff0c;不管是学校、企业、商场、小区还是机关单位&#xff0c;都需要这种设备。 红外人体测温仪测量距离可在1-5…

etcd v3使用示例

1.简单使用 1.1 增加 set 指定某个键的值。例如: $ etcdctl set /testdir/testkey "Hello world" Hello world 复制代码支持的选项包括&#xff1a; --ttl 0 该键值的超时时间(单位为秒)&#xff0c;不配置(默认为0)则永不超时 --swap-with-value value 若该键现…

ubuntu安装V2board宝塔面板教程

ubuntu安装V2board宝塔面板教程 运行环境:ubuntu-20.04 搭建宝塔web页面环境 切到linux服务器命令行 在用户目录下创建BT目录,进入BT目录 在BT目录下执行命令 sudo wget -O install.sh http://download.bt.cn/install/install-ubuntu_6.0.sh && sudo sh install.sh…

面试题30天打卡-day06

1、什么是反射机制&#xff1f;说说反射机制的优缺点、应用场景&#xff1f; 反射机制&#xff1a;Java的反射机制是在运行状态&#xff0c;对于任意一个类&#xff0c;都能够动态的获得这个类的属性和方法&#xff1b;对于一个对象&#xff0c;都能动态的调用它当中的方法和属…

几十个简要的游戏案例分析

文章目录 一、 介绍二、 影响游戏体验的因素三、 游戏能爆火的因素1.影响游戏爆火因素的排名2.玩游戏的两种经典心理3.经典案例分析Qq农场植物大战僵尸水果忍者召唤神龙羊了个羊 4.游戏公司可借鉴的经验 四、 几十款游戏的多方面分析FC红白游戏机十二人街霸热血高校系列魂斗罗系…

搭建系统。

前言&#xff1a;为了应对大量简单页面的生产需求而设计的一种工具型产品就是搭建系统&#xff0c;它的目标非常明确&#xff0c;就是快速生产大量的页面。 这节我们来了解搭建系统 搭建系统的设计 几种常见的搭建系统的设计 第一种&#xff0c;是模板化搭建&#xff0c;由前…

二极管反向恢复过程详细解析

二极管反向恢复过程&#xff0c;现代脉冲电路中大量使用晶体管或二极管作为开关, 或者使用主要是由它们构成的逻辑集成电路。而作为开关应用的二极管主要是利用了它的通(电阻很小)、断(电阻很大) 特性, 即二极管对正向及反向电流表现出的开关作用。二极管和一般开关的不同在于,…

ThreadLocal InheritableThreadLocal TransmittableThreadLocal的使用以及原理

ThreadLocal 每个线程向ThreadLocal设置值&#xff0c;再取值&#xff0c;实现线程之间的隔离 public class ThreadLocalCase1 {private static ThreadLocal<Integer> threadLocal new ThreadLocal<>();public static void main(String[] args) {Random random …

JavaScript的基础语法学习

文章目录 一、JavaScript let 和 const二、JavaScript JSON三、javascript:void(0) 含义四、JavaScript 异步编程总结 一、JavaScript let 和 const let 声明的变量只在 let 命令所在的代码块内有效。 const 声明一个只读的常量&#xff0c;一旦声明&#xff0c;常量的值就不…

APIs -- DOM正则表达式

1. 介绍 正则表达式(Regular Expression)是用于匹配字符串中字符组合的模式。在JavaScript中&#xff0c;正则表达式也是对象通常用来查找、替换那些符合正则表达式的文本&#xff0c;许多语言都支持正则表达式。正则表达式在JavaScript中的使用场景: 例如验证表单:用户名表单…

MyBatis --- 缓存、逆向工程、分页插件

一、MyBatis的缓存 1.1、MyBatis的一级缓存 一级缓存是SqlSession级别的&#xff0c;通过同一个SqlSession查询的数据会被缓存&#xff0c;下次查询相同的数据&#xff0c;就会从缓存中直接获取&#xff0c;不会从数据库重新访问 使一级缓存失效的四种情况&#xff1a; 1、…

ElasticSearch——详解主从模式,以及主节点的选取算法(一)

详解主从模式&#xff0c;以及主节点的选取算法 Discovery模块负责发现集群中的节点&#xff0c;以及选择主节点。 ES支持多种不同Discovery类型选择&#xff0c;内置的实现称为Zen Discovery&#xff0c;其他的包括公有云平台亚马逊的EC2、谷歌的GCE等。本文讨论内置的Zen Di…

rviz 可视化手机 IMU

原博客&#xff1a;https://www.cnblogs.com/hitcm/p/5616364.html 原代码&#xff1a;https://github.com/hitcm/Android_Camera-IMU.git 上面说的不太详细&#xff0c;出现了无法可视化 IMU 转交的情况。git 的 issue 中也有人遇到这个问题。本博客记录了自己如何克服 BUG 并…