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

Leetcode刷题之经典双指针问题

        光是话不行,要紧的是做。                           ——鲁迅

目录

 

一.什么是双指针问题?

二.最接近的三数之和

第一种暴力法:

第二种双指针: 

三.移除元素

第一种暴力法:

第二种双指针: 

四.盛最多水的容器 

一.什么是双指针问题?

双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。

换言之,双指针法充分使用了数组有序这一特征,从而在某些情况下能够简化一些运算。


第一种快慢指针:

快慢指针也是双指针,但是两个指针从同一侧开始遍历数组,将这两个指针分别定义为快指针(fast)和慢指针(slow),两个指针以不同的策略移动,直到两个指针的值相等(或其他特殊条件)为止,如 fast 每次增长两个,slow 每次增长一个。
 

第二种对撞指针:

对撞指针是指在数组中,将指向最左侧的索引定义为左指针(left),最右侧的定义为右指针(right),然后从两头向中间进行数组遍历。


对撞数组适用于连续数组和字符串,也就是说当你遇到题目给定连续数组和字符床时,应该第一时间想到用对撞指针解题。

二.最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。


示例 2:

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

做题链接:最接近的三数之和

第一种暴力法:

求最接近的三数之和,使用三个循环依次遍历整个数组,枚举出所有的可能,从而推算出最接近的,但是此算法时间复杂度为O(N^3)。力扣上是运行不过的,这里我们只是作为一个参考。 

#include<stdio.h>
#include<math.h>
int threeSumClosest(int* nums, int numsSize, int target)
{int i = 0;int j = 0;int k = 0;int temp = nums[0] + nums[1] + nums[2];for (i = 0; i < numsSize; i++){for (j = i + 1; j < numsSize; j++){for (k = j + 1; k < numsSize; k++){int sum = nums[i] + nums[j] + nums[k];if (abs(sum- target) < abs(temp - target))//abs是绝对值的意思{//如果sum- target的绝对值更小,说明sum更接近target的值temp = sum;}}}}return temp;
}
int main()
{int nums[10] = { 0 };int numsSize = 0;int target = 0;scanf("%d %d", &numsSize, &target);int i = 0;for (i = 0; i < numsSize; i++){scanf("%d", &nums[i]);}int ret = threeSumClosest(nums, numsSize, target);printf("%d", ret);return 0;
}

第二种双指针: 

此算法需要先把数组从小到大进行排序,排好序之后。因为这里是三个数,而双指针操作的是两个数,这里我们就需要先定下一个数,然后左指针指向定的下一个数,右指针指向最右边的数。

int cmp_int(const void* a, const void* b)
{return *(int*)a - *(int*)b;
}
int threeSumClosest(int* nums, int numsSize, int target) {qsort(nums, numsSize, sizeof(int), cmp_int);//使用快排进行排序int best = nums[0] + nums[1] + nums[2];for (int i = 0; i < numsSize; i++){int left = i + 1;int right = numsSize - 1;while (left < right){int min = nums[i] + nums[left] + nums[left + 1];//先来算出最小值,如果target比最小值还小,后面代码就不用进行了,直接breakif (target < min){if (abs(min - target) < abs(best - target)){best = min;}break;}int max = nums[i] + nums[right] + nums[right - 1];//如果target比最大值还大,直接breakif (target > max){if (abs(max - target) < abs(best - target)){best = max;}break;}int sum = nums[i] + nums[left] + nums[right];if (sum == target)//有可能会出现相等的情况,相等了就直接返回{return target;}if (abs(sum - target) < abs(best - target)){best = sum;}if (sum > target){right--;}else{left++;}}}return best;
}

三.移除元素

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

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

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

示例 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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

做题链接:移除元素

第一种暴力法:

遍历数组,如果在数组中找到了val,则把数组后面的内容全部向前移动一位,把val给覆盖掉,依次类推,直到把数组里面等于val的值全部给覆盖掉。

最坏的情况就是数组里面的值全是val,则时间复杂度为O(N^2)。

int removeElement(int* nums, int numsSize, int val)
{int i = 0;int j = 0;int count = 0;for (i = 0; i < numsSize; i++){if (nums[i] == val){for (j = i; j < numsSize-1; j++){nums[j] = nums[j + 1];}i--;//使下一次判断时,回到上次判断的位置numsSize--;//进入一次if语句,则数组的大小就会减少一个}}return numsSize;
}
int main()
{int nums[10] = { 0 };int numsSize = 0;int val = 0;scanf("%d %d", &numsSize, &val);int i = 0;for (i = 0; i < numsSize; i++){scanf("%d", &nums[i]);}int ret = removeElement(nums, numsSize,val);int j = 0;for (j = 0; j < ret; j++){printf("%d ", nums[j]);}return 0;
}

第二种双指针: 

int removeElement(int* nums, int numsSize, int val)
{int dst=0;int src=0;while(dst<numsSize){if(nums[dst]!=val){nums[src]=nums[dst];src++;}dst++;}return src;
}

四.盛最多水的容器 

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

 

示例1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为7*7= 49。


示例 2:

输入:height = [1,1]
输出:1

做题链接:盛最多水的容器

这道题还是使用双指针的方法来求:

int max(int x, int y)
{return x > y ? x : y;
}
int min(int x, int y)
{return x < y ? x : y;
}
int maxArea(int* height, int heightSize)
{int left = 0;int right = heightSize - 1;int maxarea = 0;while (left < right){maxarea = max(maxarea, min(height[left], height[right]) * (right - left));//min是求装水的最大高度,肯定以最低的那条线为准,不然就漏水了//right-left就是底边的长if (height[left] > height[right])//说明height[right]此时是短的那根线,需要right--,往前找其他的线right--;elseleft++;}return maxarea;
}

你的点赞,评论,收藏加关注都是我前进的动力。感谢!

相关文章:

Leetcode刷题之经典双指针问题

光是话不行&#xff0c;要紧的是做。 ——鲁迅 目录 一.什么是双指针问题&#xff1f; 二.最接近的三数之和 第一种暴力法&#xff1a; 第二种双指针&#xff1a; 三.移除元素 第一种暴力法&#xff1a; 第二种双指针&#xff1a; 四.盛最…...

C语言学习之路--指针篇

目录一、前言二、指针一、指针是什么1、指针的重要理解2、指针变量3、其他问题二、指针和指针类型1、指针—整数2、指针的解引用三、野指针1、野指针成因2、如何规避野指针四、指针的运算1、指针—指针2、指针的关系运算五、指针和数组六、二级指针七、指针数组一、前言 本人是…...

吃透Java面试题,建议收藏

本文已经收录到Github仓库&#xff0c;该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点&#xff0c;欢迎star~ Github地址&#xff1a;https://github.com/…...

华为OD机试题,用 Java 解【最差产品奖】问题 | 含解题说明

华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典本篇题目:最差产品奖 题目 A 公司准备对…...

Redis缓存优化

数据库在用户数量多&#xff0c;系统访问量大的时候&#xff0c;系统性能会下降&#xff0c;用户体验差。1.缓存优化作用&#xff1a;1.降低数据库的访问压力2.提高系统的访问性能3.从而提高用户体验实现思路&#xff1a;1.先查询缓存2.如果缓存有数据&#xff0c;直接返回3.如…...

少儿Python每日一题(23):楼梯问题

原题解答 本次的题目如下所示: 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,走完n阶台阶共有多少种不同的走法? 输入格式: 输入楼梯的阶梯数n 输出格式: 输出不同走法的个数 输入样例: 10 输出样例: 89 这是一道非常经典的题目,我们可以先寻找一下上楼梯的规律…...

【Leetcode】队列实现栈和栈实现队列

目录 一.【Leetcode225】队列实现栈 1.链接 2.题目再现 3.解法 二.【Leetcode232】栈实现队列 1.链接 2.题目再现 3.解法 一.【Leetcode225】队列实现栈 1.链接 队列实现栈 2.题目再现 3.解法 这道题给了我们两个队列&#xff0c;要求去实现栈&#xff1b; 首先&…...

(一)Tomcat源码阅读:查看官网,厘清大概轮廓

一、进入官网 点击以下链接进入官网:Apache Tomcat - Welcome!,点击介绍进入介绍&#xff0c;查看tomcat的项目结构。 二、查看项目结构 进入介绍后&#xff0c;我们可以看到下面的这些东西&#xff0c;这些对于tomcat是比较重要的&#xff0c;我们要一一对其进行解读。 这段…...

刷题记录(2023.3.14 - 2023.3.18)

[第五空间 2021]EasyCleanup 临时文件包含考点 分析源码&#xff0c;两个特殊的点&#xff0c;一个是 eval&#xff0c;另一个是 include eval 经过了 strlen filter checkNums 三个函数 include 经过了 strlen filter 两个函数 filter 检测是否包含特定的关键字或字符 fun…...

http协议 - 笔记

1 http协议 -- post,get,delete 如何使用http协议post - /api/v1/User/1 要使用 HTTP 协议 POST 方法向 /api/v1/User/1 发送请求,您可以使用一个 HTTP 客户端(例如 Postman、cURL 或浏览器扩展程序)并按照以下步骤操作: 打开您的 HTTP 客户端。在 URL 地址栏中输入 /a…...

第十八天 Vue-前端工程化总结

目录 Vue-前端工程化 1. 前后端分离开发 1.1 介绍 1.2 Yapi 2. 前端工程化 2.1 环境准备 2.2 Vue项目简介 2.3 Vue项目开发流程 3. Vue组件库Element 3.1 快速入门 3.2 常用组件 3.3 案例 Vue-前端工程化 前面我们已经讲解了HTML、CSS、JavaScript以及Vue等知识。已…...

python网上选课系统django-PyCharm

学生选课信息管理系统&#xff0c;可以有效的对学生选课信息、学生个人信息、教师个人信息等等进行管理。 开发语言&#xff1a;Python 框架&#xff1a;django Python版本&#xff1a;python3.7.7 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat11 开发软件&#x…...

Java序列化与反序列化

优秀博文&#xff1a;IT-BLOG-CN 序列化&#xff1a;把对象转换为字节序列存储于磁盘或者进行网络传输的过程称为对象的序列化。 反序列化&#xff1a;把磁盘或网络节点上的字节序列恢复到对象的过程称为对象的反序列化。 一、序列化对象 【1】必须实现序列化接口Serializabl…...

【网络】网络层协议——IP

目录网络层IP协议IP基础知识IP地址IP报头格式网段划分CIDR特殊的IP地址IP地址的数量限制私有IP地址和公有IP地址路由IP总结网络层 在复杂的网络环境中确定一个合法的路径。 IP协议 IP协议作为整个TCP/IP中至关重要的协议&#xff0c;主要负责将数据包发送给最终的目标计算机…...

安装kubernetes

master110.10.10.10docker、kubelet、kubeadm、kubectlmaster210.10.10.11docker、kubelet、kubeadm、kubectlnode110.10.10.12docker、kubelet、kubeadm、kubectlnode210.10.10.13docker、kubelet、kubeadm、kubectl 1.关闭防火墙&#xff08;所有节点执行&#xff09; syste…...

三维点云转深度图

文章目录 目录 一、算法原理 算法流程 二、代码实现 1.Python代码 2....

Qt音视频开发27-ffmpeg视频旋转显示

一、前言 用手机或者平板拍摄的视频文件&#xff0c;很可能是旋转的&#xff0c;比如分辨率是1280x720&#xff0c;确是垂直的&#xff0c;相当于分辨率变成了720x1280&#xff0c;如果不做旋转处理的话&#xff0c;那脑袋必须歪着看才行&#xff0c;这样看起来太难受&#xf…...

python例程:《彩图版飞机大战》程序

目录开发环境要求运行方法《彩图版飞机大战》程序使用说明源码示例源码及说明文档下载路径开发环境要求 本系统的软件开发及运行环境具体如下。 操作系统&#xff1a;Windows 7、Windows 10。 Python版本&#xff1a;Python 3.7.1。 开发工具&#xff1a;PyCharm 2018。…...

【前端八股文】JavaScript系列:Set、Map、String常用属性方法

文章目录Set概念与arr的比较属性和方法并集、交集、差集Map概念属性和方法String用索引值和charAt()的区别charAt()和charCodeAt()方法的区别5个查找方法的区别如何把字符串分割为数组3个截取方法的区别大小写转换3个模式匹配方法&#xff08;正则表达式&#xff09;3个移除字符…...

跳跃-动态规划问题

跳跃-动态规划问题1、题目描述2、解题思路2.1 解法一&#xff1a;动态规划2.2 解法二&#xff1a;DFS深度优先搜索最大权值1、题目描述 小蓝在一个 n 行 m 列的方格图中玩一个游戏。 开始时&#xff0c;小蓝站在方格图的左上角&#xff0c;即第 11 行第 11 列。 小蓝可以在方格…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解

文章目录 一、开启慢查询日志&#xff0c;定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...

GAN模式奔溃的探讨论文综述(一)

简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...

CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx

“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网&#xff08;IIoT&#xff09;场景中&#xff0c;结合 DDS&#xff08;Data Distribution Service&#xff09; 和 Rx&#xff08;Reactive Extensions&#xff09; 技术&#xff0c;实现 …...