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

双指针解题

验证回文数(验证回文数-CSDN博客)和判断在子序列(判断子序列-CSDN博客)已经在之前进行了计算,今天有三个新的双指针问题:

两数之和II—输入有序数组

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列  ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1  index2

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1:

输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2:

输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3:

输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 

思路:

双指针的思想,nums是一个有序的数组 因此我们可以使用这个特性,即数据从小到大递增,创建连个指针left指向0,right指向数组末尾 若它们所指向的数据和为target,直接返回 ;否则若值小于target,则left++ 否则 right--;

 public int[] twoSum(int[] numbers, int target) {int left=0,right=numbers.length-1;while(left<right){int sum=numbers[left]+numbers[right];if(sum==target)return new int []{left+1,right+1};else if(sum<target)left++;elseright--;}return new int[0];
}

盛水最多的容器

给定一个长度为 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]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

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

思路:

最笨方法就是暴力解法:就是经过两次循环计算出所有的储水量,找出其中最大的并返回。但可能会超时

在这里我们可以使用双指针,left指向0,right指向height.length-1; 初始化res=0,表示当前的盛水量,使用Math.min(height[left],height[right])*(right-left)来计算盛水量,=并与res进行比较将较大真存在res中,然后移动left或right :若height[left]<=height[right],就left++ 否则right--(是因为每次都是有Math.min来计算,所以移动较短的哪一方,若移动较长的哪一方,盛水量肯定减少)直到left>=right

public int maxArea(int[] height) {int left=0,right=height.length-1;int res=0;while(left < right){int k=Math.min(height[left],height[right])*(right-left);if(k>res)res=k;if(height[left]<=height[right])left++;elseright--;}return res;
}

三数之和

在看三数之和之前,可以看看两数之和

两数之和:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

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

思路:

  第一种:暴力解法 ,循环求解
public int[] twoSum(int[] nums, int target) {for(int i=0;i<nums.length;i++){for(int j=i+1;j<nums.length;j++){if(nums[i]+nums[j]==target)return new int []{i,j};}}return new int [0];
}
第二种:哈希算法

  创建一个hashmap存储数据和其对应的下标,刚开始时hashmap为空,循环遍历数组for(int i=0;i<nums.length;i++) 若hashmap中包含target-nums[i] 则返回其下标和i 否则就将其加入到hashmap中(这里我刚开始不懂,此时hashmap为空怎么去寻找数据?为target是由两数在组成的,比如9=2+7,第一次访问2,map中找不到7,将2加入到map中,当访问7时就可以在map中找到2 )

public int[] twoSum(int[] nums, int target) {hashMap<Integer> map=new HashMAp<>();for(int i=0;i<nums.length;i++){if(map.containsKey(target-nums[i]){return new int[]{map.get(target-nums[i],i};hashmap.put(nums[i],i);}return new int nums[0];
}

三数之和解题

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

思路:

1、将三数之和变成一个数固定的两数之和

2、如何保证元素不重复??

     首先需要对数组进行排序Ayyays.sort(nums),这样就变成不递减的数组

     然后在进行遍历的过程中需要注意 此时遍历的数不能和它的前面一个数相同

   最后可以借鉴有序数组的两数之和进行寻找

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list=new AyyayList<List<Integer>>();int first=0;Arrays.sort(nums); // 进行排序for(first=0;first<nums.length;first++){//固定第一个数if(first>0 && nums[first]==nums[first-1]) //此时遍历的数不能和它的前面一个数相同,否则会出现重复return continue;  int target=0-nums[i]; //其余两数之和int thrid=nums.length-1; //第三个指针指向数组末尾for(int second=first+1; second<nums.length;second++){if(second>first+1 && nums[second]==nums[second-1])continue;while(second<thrid && nums[second]+nums[thrid]>target) //因为此时是从小到大排序的 ,所以当nums[second]+nums[thrid]不大于target就有可能找到那个数了thrid--;if(second==thrid)break;if(nums[second]==nums[thrid]){List<Integer> res=new AyyayList<>();res.add(nums[first]);res.add(nums[second]);res.add(nums[thrid]);list.add(res);}}}return list;
}

相关文章:

双指针解题

验证回文数&#xff08;验证回文数-CSDN博客&#xff09;和判断在子序列&#xff08;判断子序列-CSDN博客&#xff09;已经在之前进行了计算&#xff0c;今天有三个新的双指针问题&#xff1a; 两数之和II—输入有序数组 给你一个下标从 1 开始的整数数组 numbers &#xff0…...

【Text2SQL 论文】DIN-SQL:分解任务 + 自我纠正 + in-context 让 LLM 完成 Text2SQL

论文&#xff1a;DIN-SQL: Decomposed In-Context Learning of Text-to-SQL with Self-Correction ⭐⭐⭐⭐ NeurIPS 2023, arXiv:2304.11015 Code: Few-shot-NL2SQL-with-prompting | GitHub 文章目录 一、论文速读1.1 Schema Linking Module1.2 Classification & Decompo…...

基于Springboot+vue实现的汽车服务管理系统

作者主页&#xff1a;Java码库 主营内容&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app等设计与开发。 收藏点赞不迷路 关注作者有好处 文末获取源码 技术选型 【后端】&#xff1a;Java 【框架】&#xff1a;spring…...

ROS2从入门到精通4-3:全局路径规划插件开发案例(以A*算法为例)

目录 0 专栏介绍1 路径规划插件的意义2 全局规划插件编写模板2.1 构造规划插件类2.2 注册并导出插件2.3 编译与使用插件 3 全局规划插件开发案例(A*算法)常见问题 0 专栏介绍 本专栏旨在通过对ROS2的系统学习&#xff0c;掌握ROS2底层基本分布式原理&#xff0c;并具有机器人建…...

Java学习【认识异常】

Java学习【认识异常】 认识异常异常的种类异常的作用 异常的处理方式JVM默认的处理方式捕获异常finally 多个异常的处理异常中的方法抛出异常 自定义异常 认识异常 在Java中&#xff0c;将程序执行过程中发生的不正常行为称为异常 异常的种类 Error代表的是系统级别的错误&a…...

uniapp+h5 ——微信小程序页面截屏保存在手机

web-view 需要用到 web-view &#xff0c;类似于iframe&#xff0c; 将网页嵌套到微信小程序中&#xff0c;参数传递等&#xff1b; 示例&#xff08;无法实时传递数据&#xff09;&#xff0c;页面销毁时才能拿到h5传递的数据&#xff0c;只能利用这点点击跳转到小程序另一个…...

三、基于图像分类预训练编码及图神经网络的预测模型 【框图+源码】

背景&#xff1a; 抽时间补充&#xff0c;先挖个坑。 一、模型结构 二、源码...

Linux - 高级IO

目录 理解五种IO模型非阻塞IO的设置多路转接之select 实现一个简易的select服务器select服务器的优缺点 多路转接之poll 实现一个简易的poll服务器poll服务器的优缺点 多路转接之epoll epoll原理epoll的优势用epoll实现一个简易的echo服务器 epoll的LT和ET工作模式 什么是LT和…...

面试题:说一下 http 报文都有哪些东西?

面试题&#xff1a;说一下 http 报文都有哪些东西&#xff1f; HTTP 是传输超文本&#xff08;实际上除了 HTML&#xff0c;可以传输任何类型的文件&#xff0c;如视频、音频、文本等&#xff09;的协议&#xff0c;是一组用于浏览器-服务器之间数据传输的规则。 HTTP 位于 OS…...

开山之作!Python数据与算法分析手册,登顶GitHub!

若把编写代码比作行军打仗&#xff0c;那么要想称霸沙场&#xff0c;不能仅靠手中的利刃&#xff0c;还需深谙兵法。 Python是一把利刃&#xff0c;数据结构与算法则是兵法。只有熟读兵法&#xff0c;才能使利刃所向披靡。只有洞彻数据结构与算法&#xff0c;才能真正精通Pyth…...

编译安装gcc-11及可能遇到的bug

编译安装脚本 GCC_VERSION11.1.0 PACKAGE_DIR/path/to/gcc/source/code GCC_DIR$PACKAGE_DIR/gcc-$GCC_VERSION GCC_INSTALL_DIR/path/to/install/gccmkdir -p $GCC_INSTALL_DIR cd $GCC_INSTALL_DIR rm -rf * cd $PACKAGE_DIR rm -rf gcc-$GCC_VERSION if [ ! -f "gcc-$…...

vue项目引入json/js文件批量或单个方法

vue项目 json // 方式一 &#xff1a; 将文件内容完整的引入 import json from ./src/assets/xxx.json console.log(json) console.log(---)// 方式二 &#xff1a; 部分引入-名称必须是文件中定义的key import {name1,name2} from ./src/assets/xxx.json console.log(name1)…...

守护任务用来防止资源冲突

背景&#xff1a;有三个任务&#xff0c;他们都需要操作数码管。每个任务对应三个数码管&#xff0c;共9个数码管。硬件上9个数码管的控制使用一套硬件完成。 策略&#xff1a;每个任务都往自己的队列里面发数据&#xff0c;单独建立一个监听任务&#xff1a;处理所有队列的数…...

fast admin实现多数据库导入数据

思路 1创建多数据库连接 2后端的前台代码能使用get或者post请求传递选中数据给后台 3后台能够接收到 4后台接收到id或者全字段数据后对数据进行处理&#xff0c;然后使用多数据库操作将其存入第二个数据库 实现 1config文件下创建新数据库连接 db_config2 > [// 数据库类…...

NLP基础——序列模型(动手学深度学习)

序列模型 定义 序列模型是自然语言处理&#xff08;NLP&#xff09;和机器学习领域中一类重要的模型&#xff0c;它们特别适合处理具有时间顺序或序列结构的数据&#xff0c;例如文本、语音信号或时间序列数据。 举个例子&#xff1a;一部电影的评分在不同时间段的评分可能是…...

机器学习AI大模型的开源与闭源:哪个更好?

文章目录 前言一、开源AI模型1.1 开源的优点1.2 开源的缺点 二、闭源AI模型2.1 闭源的优点2.2 闭源的缺点 三、开源与闭源的平衡3.1 开源与闭源结合的案例3.2 开源与闭源的战略选择 小结 前言 在过去的几年里&#xff0c;人工智能&#xff08;AI&#xff09;和机器学习&#xf…...

关于大模型多轮问答的两种方式

前言 大模型的多轮问答难点就是在于如何精确识别用户最新的提问的真实意图&#xff0c;而在常见的使用大模型进行多轮对话方式中&#xff0c;我接触到的只有两种方式&#xff1a; 一种是简单地直接使用 user 和 assistant 两个角色将一问一答的会话内容喂给大模型&#xff0c…...

达梦数据库相关SQL及适配Mysql配置总结

&#x1f353; 简介&#xff1a;java系列技术分享(&#x1f449;持续更新中…&#x1f525;) &#x1f353; 初衷:一起学习、一起进步、坚持不懈 &#x1f353; 如果文章内容有误与您的想法不一致,欢迎大家在评论区指正&#x1f64f; &#x1f353; 希望这篇文章对你有所帮助,欢…...

Centos7.9实现多台机器ssh免密登录

1.本机&#xff08;172.16.10.228&#xff09;先生成密钥对 ssh-keygen -t rsa 2.执行命令&#xff0c;把本机公钥拷贝到远程机器 ssh-copy-id rootdistinctIp 3.查看一下远程机器 、/root/.ssh/authorized_keys文件 cat /root/.ssh/authorized_keys 会看到里边多了个公钥…...

Unity3D DOTS JobSystem物理引擎的使用详解

前言 Unity3D DOTS&#xff08;Data-Oriented Technology Stack&#xff09;是Unity引擎的一项新技术&#xff0c;旨在提高游戏性能和扩展性。其中的Job System是一种用于并行处理任务的系统&#xff0c;可以有效地利用多核处理器的性能。在本文中&#xff0c;我们将重点介绍如…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...