Leetcode刷题-数组(二分法、双指针法、窗口滑动)
数组
1、二分法
- 704. 二分查找 - 力扣(LeetCode)
需要注意区间的问题。首先在最外面的循环判断条件是left<=right。那就说明我们区间规定的范围就是【left,right】
属于是左闭右闭!!!!!!
那之后在判断target和我们数组中的num [ mid ] 大小关系之后,再重新调整right,以及left的时候,应该是left = mid + 1,right = mid - 1
- while (left <= right) 要使⽤ <= ,因为left == right是有意义的
- 所以使⽤ <= if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]⼀定不是target,那么接 下来要查找的左区间结束下标位置就是 middle - 1
2、移除元素(双指针-同向)
- 27. 移除元素 - 力扣(LeetCode)
除了可以暴力两层循环这么去从后往前覆盖,从而消除掉目标元素
还可以使用双指针法:快慢指针(重点是理解快慢指针什么含义)!!!!!!!!
-
快指针:遍历数组,去寻找新数组的元素,就是通过这个指针去找出来,除了目标元素的所有值
-
慢指针:用于指向新数组的下标,就是通过快指针找到符合条件的元素(不是需要删除的元素)就将其放进“新数组”,慢指针指向的下标就会+1
int slow = 0;
for(int fast = 0; fast < nums.length; fast++){if(nums[fast] != target){nums[slow++] = nums[fast];}
}
3、有序数组的平方(双指针-相向)
题目需求:一个有序数组,存在有负数,所有元素依次取平方要求最后还是有序
- 977. 有序数组的平方 - 力扣(LeetCode)
根据题意可以知道,最大值肯定出现在数组的左右两侧
所以还是想到用双指针的思路,两个指针分别指向数组的开头和结尾,然后向中间移动
符合条件的放进新的数组中
public int[] sortedSquares(int[] nums) {int k = nums.length - 1; int[] res = new int[k+1]; //注意数组长度定义for(int i=0,j=k; i<=j; ){if(nums[i]*nums[i] > nums[j]*nums[j]){res[k--] = nums[i] * nums[i];i++;}else {res[k--] = nums[j] * nums[j];j--;}}return res;
}
4、⻓度最⼩的⼦数组(滑动窗口)
- 209. 长度最小的子数组 - 力扣(LeetCode)

除了暴力解决,还有滑动窗口思路
其实也就是双指针的思路,不过是取两个指针中间的一个集合,像是一个滑动的窗口
最后目标的长度就是:指针2 - 指针1 + 1
然后需要明确一下两个指针的含义:
- 指针1:for循环里面的指针 j ,这个是指向这个区间的终止位置的,我们的目标是通过对开始位置 指针i 进行操作然后更新最小长度
- 指针2:这个用来标记开始位置,和指针1结合使用
1、窗⼝的起始位置如何移动:如果当前窗⼝的值⼤于s了,窗⼝就要向前移动了(也就是该缩⼩了)。
2、**窗⼝的结束位置如何移动:**窗⼝的结束位置就是遍历数组的指针,也就是for循环⾥的索引。
解题的关键在于 窗⼝的起始位置如何移动,相当于是sum一边吐出之前区间中最开始的数据,然后再加上一下个数据,之后再利用标记开始位置的指针2,再取判断
class Solution {public int minSubArrayLen(int target, int[] nums) {int i = 0; // 滑动窗⼝起始位置,也就是指针2int sum = 0; // 滑动窗⼝数值之和int minLen = Integer.MAX_VALUE; for(int j = 0; j < nums.length; j++){sum += nums[j];while(sum >= target){int len = j - i + 1;minLen = Math.min(minLen,len);sum -= nums[i]; // 这⾥体现出滑动窗⼝的精髓之处,不断变更i(⼦序列的起始位置)i++;}}return minLen == Integer.MAX_VALUE ? 0 : minLen; // 如果result没有被赋值的话,就返回0,说明没有符合条件的⼦序列}
}
5、螺旋矩阵II (知道思路即可,有空再练代码)
- 59. 螺旋矩阵 II - 力扣(LeetCode)

⾯试中出现频率较⾼的题⽬,本题并不涉及到什么算法,就是模拟过程,但却⼗分考察对代码的 掌控能⼒。
这里容易遇到的问题是:
就是因为在画每⼀条边的时候,⼀会左开右闭,⼀会左闭右闭,⼀会⼜来左闭右开,岂能不乱。
比如第一次是1、2、3,第二次遍历第二条边又成了4、5,不包含起始节点了,这样就很乱,肯定会出问题
int[][] res = new int[n][n]; // 使⽤vector定义⼀个⼆维数组
int startx = 0, starty = 0; // 定义每循环⼀个圈的起始位置
int loop = n / 2; // 每个圈循环⼏次,例如n为奇数3,那么loop = 1 只是循环⼀圈,矩阵中间的值需要单独处理
int mid = n / 2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)
int count = 1; // ⽤来给矩阵中每⼀个空格赋值
int offset = 1; // 需要控制每⼀条边遍历的⻓度,每次循环右边界收缩⼀位
int i,j;
while (loop > 0) {i = startx;j = starty;// 下⾯开始的四个for就是模拟转了⼀圈// 模拟填充上⾏从左到右(左闭右开)for (j = starty; j < n - offset; j++) {res[startx][j] = count++;}// 模拟填充右列从上到下(左闭右开)for (i = startx; i < n - offset; i++) {res[i][j] = count++;}// 模拟填充下⾏从右到左(左闭右开)for (; j > starty; j--) {res[i][j] = count++;}// 模拟填充左列从下到上(左闭右开)for (; i > startx; i--) {res[i][j] = count++;}// 第⼆圈开始的时候,起始位置要各⾃加1, 例如:第⼀圈起始位置是(0, 0),第⼆圈起始位置是(1, 1)startx++;starty++;// offset 控制每⼀圈⾥每⼀条边遍历的⻓度offset += 1;loop--;
}
// 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
if (n % 2 != 0) {res[mid][mid] = count;
}
return res;
注:本篇是跟着代码随想录刷题练习,不过是自己的刷题总结,使用的刷题语言是Java
相关文章:
Leetcode刷题-数组(二分法、双指针法、窗口滑动)
数组 1、二分法 704. 二分查找 - 力扣(LeetCode) 需要注意区间的问题。首先在最外面的循环判断条件是left<right。那就说明我们区间规定的范围就是【left,right】 属于是左闭右闭!!!!!&…...
STM32学习和实践笔记(4): 分析和理解GPIO_InitTypeDef GPIO_InitStructure (b)
继续上篇博文:STM32学习和实践笔记(4): 分析和理解GPIO_InitTypeDef GPIO_InitStructure (a)-CSDN博客 往下写, 为什么:当GPIO_InitStructure.GPIO_PinGPIO_Pin_0 ; 时,其实就是将对应的该引脚的寄存器地…...
数据仓库——事实表
数据仓库基础笔记思维导图已经整理完毕,完整连接为: 数据仓库基础知识笔记思维导图 事实表 事务事实表 事务事实表用于跟踪事件,通过存储事实和与之关联的维度细节,允许单独或聚集地研究行为。粒度稀疏性包含可加事实 无事实的…...
人工智能常用的编程语言有哪些?
人工智能常用的编程语言包括Python、Java、C、R、Lisp和Prolog等。具体选择取决于项目需求、技术背景和性能要求。 Python是AI领域的明星语言,由于其简洁易懂的语法、丰富的库支持以及庞大的社区资源,适用于机器学习、深度学习和自然语言处理等领域。 …...
【Leetcode每日一题】模拟 - 提莫攻击(难度⭐)(45)
1. 题目解析 题目链接:495. 提莫攻击 2.算法原理 一、分情况讨论 要计算中毒的总时长,我们需要考虑时间点之间的差值,并根据这些差值来确定中毒的实际持续时间。 情况一:差值大于等于中毒时间 假设你的角色在时间点A中毒&#…...
OPPO云VPC网络实践
1 OPPO 云网络现状 随着OPPO业务的快速发展,OPPO云规模增长迅速。大规模虚拟实例的弹性伸缩、低延时需求对网络提出了诸多挑战。原有基于VLAN搭建的私有网络无法解决这些问题,给网络运维和业务的快速上线带来了挑战。 梳理存在的主要问题如下…...
力扣(数组)找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。 示例 1: 输入:nums [4,3,2,7,8,2,3,1] 输出:[5,6]示例 2&am…...
每日面经分享(Spring Boot: part3 Service层)
SpringBoot Service层的作用 a. 封装业务逻辑:Service层负责封装应用程序的业务逻辑。Service层是控制器(Controller)和数据访问对象(DAO)之间的中间层,负责处理业务规则和业务流程。通过将业务逻辑封装在S…...
k8s的pod访问service的方式
背景 在k8s中容器访问某个service服务时有两种方式,一种是把每个要访问的service的ip注入到客户端pod的环境变量中,另一种是客户端pod先通过DNS服务器查找对应service的ip地址,然后在通过这个service ip地址访问对应的service服务 pod客户端…...
shell脚本发布docker-nginx vue2 项目示例
docker、git、node.js安装略过。 使git pull或者git push不需要输入密码操作方法 nginx安装在docker容器里面,参见:https://blog.csdn.net/HSJ0170/article/details/128631155 姊妹篇(宿主机nginx,非docker-nginx)&am…...
【THM】Nmap Basic Port Scans(基本端口扫描)-初级渗透测试
介绍 本房间是Nmap系列的第二个房间(网络安全简介模块的一部分)。 1.Nmap实时主机发现 2.Nmap基本端口扫描 3.Nmap高级端口扫描 4.Nmap后端口扫描 在之前的房间里,我们专注于发现在线系统。到目前为止,我们已经介绍了Nmap扫描的三个步骤: 枚举目标发现活动主机反向-…...
Groovy结合Java在生产中的落地实战
Groovy简介 Groovy是用于Java虚拟机的一种敏捷的动态语言,是一种成熟的面向对象编程语言,又是一种纯粹的脚本语言。Groovy运行在JVM环境上,在语法上兼具java 语言和脚本语言特点,大大简化了语法。同时又具有闭包和动态语言中的其…...
达梦数据库 创建外部表 [-7082]:外部表数据错误.
1:定义 外部表,是指不存在于数据库中的表。通过向达梦提供描述外部表的元数据,可以把一 个操作系统文件当成一个只读的数据库表,就像这些数据存储在一个普通数据库表中一样来 进行访问。 外部表的数据存储在操作系统中࿰…...
XUbuntu22.04之激活Linux最新Typora版本(二百二十五)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒…...
JavaScript简介
目录 概要: 说明: 学习JS的原因: JS可以干什么: 了解JavaScript: 前言: JavaScript的历史: JavaScript与ECMAScript: 如何运行JavaScript以及JavaScrip的特点: …...
使用PaddleX实现的智慧农业病虫检测项目
目录 1. 数据集解压 2.检查数据集的图片是否均可读取 3. 查看数据集的类别信息...
算法学习——LeetCode力扣图论篇1(797. 所有可能的路径、200. 岛屿数量、695. 岛屿的最大面积)
算法学习——LeetCode力扣图论篇1 797. 所有可能的路径 797. 所有可能的路径 - 力扣(LeetCode) 描述 给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特…...
【IP组播】PIM-SM的RP、RPF校验
目录 一:PIM-SM的RP 原理概述 实验目的 实验内容 实验拓扑 1.基本配置 2.配置IGP 3.配置PIM-SM和静态RP 4.配置动态RP 5.配置Anycast RP 二: RPF校验 原理概述 实验目的 实验内容 实验拓扑 1.基本配置 2.配置IGP 3.配置PIM-DM 4.RPF校…...
前端代码规范-命名规范
命名规则 camelCase(小驼峰式命名法 —— 首字母小写)PascalCase(大驼峰式命名法 —— 首字母大写)kebab-case(短横线连接式)Snake(下划线连接式) 项目名称 项目名 全部采用小写方…...
移动端APP测试常见面试题精析
现在面试测试职位,要求非常全面,那么APP测试一般需要哪些技术呢?下面总结了APP测试常见面试题: 1.Android四大组件? Activity:描述UI,并且处理用户与机器屏幕的交互。应用程序中,一个Activity就相当于手…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一:yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因,后面把yaml.safe_dump直接替换成yaml.dump,确实能保存,但出现乱码: 放弃yaml.dump,又切…...
GAN模式奔溃的探讨论文综述(一)
简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...
