【算法】双指针——leetcode盛最多水的容器、剑指Offer57和为s的两个数字


盛水最多的容器
(1)暴力解法
算法思路:我们枚举出所有的容器大小,取最大值即可。
容器容积的计算方式:
设两指针 i , j ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 j - i 。由于容器的高度由两板中的较短的板决定,因此可得容积公式 :
v = (j - i) * min( height[i] , height[j] );
class Solution {
public:int maxArea(vector<int>& height) {int n=height.size();int ret=0;//枚举出所有的容器大小for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){//计算当前的容器容量int v=(j-i)*(min(height[i],height[j]));ret=max(ret,v);//取最大容量的容器}}return ret;}
};

当然由于两次遍历数组,所以时间复杂度为O(N2),会超时。
(2)对撞指针
算法思路:我们设置两个指针left、right分别指向容器的两个端点(因为这里的是数组,数组在内存中的储存是连续的,而且数组是通过它们的下表访问,所有我们可以把数组下标看成是指针进行操作)不断修改左右的端点来获得容器的最大容量。
容器的左边界为 height[left] ,右边界为 height[right] 。
我们假设「左边边界」小于「右边边界」。
水的容积会有如下变化形式:
首先容器的宽度⼀定变小。由于左边界较小,决定了水的高度。如果改变左边界,新的水面高度不确定,但是⼀定不会超过右边的柱子高度,因此容器的容积可能会增大或者减小。
但是如果改变右边界,无论右边界移动到哪⾥,新的水面的高度⼀定不会超过左边界,也就是现在左边界的所在的水面高度,但是由于容器的宽度减小,因此容器的容积一定会变小。
综上,我们不断选取左右两个边界中的较大边界,以保留当下的最有解,不断的 left++ 或right–,直到left和right相遇。
class Solution {
public:int maxArea(vector<int>& height) {int left=0;int right=height.size()-1;int ret=0;//循环条件为右边界大于左边界while(left<right){//计算当前容器的容量int v=(right-left)*(min(height[left],height[right]));ret=max(v,ret);//不断更新容器的最大容量if(height[left]>height[right]) right--;//不断更新左右高度else left++; //保留高的,舍弃较矮的高}return ret;}
};
时间复杂度:O(N)


和为s的两个数字
和两数之和不同的是,该数组中的元素是有序的,而且使用暴力解法会超时。
(1)对撞指针
这里有三种情况:
当 nums[left] + nums[right] == target时,说明找到结果,记录结果,并且返回;
当 nums[left] + nums[right] < target 时,此时 nums[right] 相当于是 nums[left] 能碰到的最大值。如果此时不符合要求,说明我们需要增加这两个数之和,所以我们让left++,再取更大的数,以来靠近我们的目标和。
当 nums[left] + nums[right] > target 时,说明我们所取的两数较大,所以我们应该减小这两个数之和,让right–,以此使得两数的总和变小,以此来靠近我们的目标和。不断比较下⼀组数据,直至两数和和目标和相等。
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int left=0;int right=nums.size()-1;while(left<right){//如果两数和等于目标值,直接返回if(nums[left]+nums[right]==target){return {nums[left],nums[right]};}//如果两数和大于目标值,right--else if(nums[left]+nums[right]>target){right--;}//如果两数和小于目标值,left++ else{left++;}}//照顾编译器,返回一个不存在的数组return {-1141514};}
};
时间复杂度:O(N)

相关文章:
【算法】双指针——leetcode盛最多水的容器、剑指Offer57和为s的两个数字
盛水最多的容器 (1)暴力解法 算法思路:我们枚举出所有的容器大小,取最大值即可。 容器容积的计算方式: 设两指针 i , j ,分别指向水槽板的最左端以及最右端,此时容器的宽度为 j - i 。由于容器…...
idea 使用debug 启动项目的时候 出现 Method breakpoints may dramatically slow down debugging
问题: 1. 写了一段时间的代码,在debug启动项目后提示:Method breakpoints may dramatically slow down debugging 但是正常启动是可以的,debug不行。 2. idea 里面的项目,很多地方都有断点,现在想要取消全部的断点…...
Tomcat的一些配置问题(server.xml/catalina.sh)
在同一机器中运行多个Tomcat时,如果不修改server.xml的端口参数,会出现端口冲突使得Tomcat异常;Tomcat默认配置中,JAVA_OPTS不会设置太大,一般需要在catalina.sh中增加一行配置来加大该参数值。 目录 1.Server.xml配置…...
飞天使-jenkins进行远程linux机器修改某个文件的思路
文章目录 jenkins配置的方式jenkins中执行shell的思路 jenkins配置的方式 jenkins中执行shell的思路 下面的脚本别照抄,只是一个思路 ipall"$ips"# 将文本参数按行输出为变量 while IFS read -r line; doecho "$line" if [[ ! -z $line ]] &…...
Revit SDK 介绍:PanelSchedule 配电盘明细表
前言 这个例子介绍 Revit 的配电盘明细表,PanelSchedule。Revit 的电器专业在国内用的并不是十分广泛,但从功能上来说还是比较完整的。 内容 这个例子里有三个命令: PanelScheduleExport - 导出配电盘明细表InstanceViewCreation - 创建配…...
Java后端实现不用pagehelper。手写分页如何实现?
Java后端实现不用pagehelper。手写分页如何实现? 如果你不使用PageHelper这样的分页插件,你可以手动实现分页逻辑。下面是一个使用Java后端手写分页的示例: 首先,确定每页显示的数据量和当前页码。 int pageSize 10; // 每页显示的数据量…...
spring 缓存
1.spring缓存注解,可以丢在controller,也可以丢在service,也可以丢在mapper。 2.手动操作缓存使用: Autowiredprivate CacheManager cacheManager;3.添加缓存 //添加缓存 Override Cacheable(cacheNames "test", key…...
vue3.0 element-plus 不同版本 el-popover 循环优化
表格内循环el-popover 渲染以后的页面,数据量很大的时候页面会卡,生成的代码: 解决思路:将el-popover提出来,不参与循环,让el-popover只渲染一次 1、以1.1.0-beta.24版为例(低版本)…...
计算机网络实验4:HTTP、DNS协议分析
文章目录 1. 主要教学内容2. HTTP协议3. HTTP分析实验【实验目的】【实验原理】【实验内容】【实验思考】 4. HTTP分析实验可能遇到的问题4.1 捕捉不到http报文4.2 百度是使用HTTPS协议进行传输4.3 Wireshark获得数据太多如何筛选4.4 http报文字段含义不清楚General(…...
敏捷项目管理如何做好Sprint Backlog?迭代管理
什么是Sprint Backlog? Sprint Backlog是Scrum的主要工件之一。在Scrum中,团队按照迭代的方式工作,每个迭代称为一个Sprint。在Sprint开始之前,PO会准备好产品Backlog,准备好的产品Backlog应该是经过梳理、估算和优先…...
实验三 图像分割与描述
一、实验目的: (1)进一步掌握图像处理工具Matlab,熟悉基于Matlab的图像处理函数。 (2)掌握图像分割方法,熟悉常用图像描述方法。 二、实验原理 1.肤色检测 肤色是人类皮肤重要特征之一ÿ…...
npm使用国内淘宝镜像的方法(两种)
一、通过命令配置 1、设置淘宝镜像源 npm config set registry https://registry.npm.taobao.org/ 2、设置官方镜像源 npm config set registry https://registry.npmjs.org 3、查看镜像使用状态: npm config get registry 如果返回https://registry.npm.taobao.org…...
05应用程序设计和文件操作
一、 给应用程序设置菜单栏 比如: 在qt中,如果想要使用菜单栏功能,那么界面的基类要选择QMainWindow,不能选择QWidget QDialog 实现菜单栏步骤如下: 第一步:在UI设计师,直接双击菜单栏 第二步:在UI设计师,修改文本内容和其他设置 进行设置 设置的效果图如下: …...
【果树农药喷洒机器人】Part8:果树对靶变量喷药实验
📢:博客主页 【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍 收藏 ⭐不迷路🙉 📢:内容若有错误,敬请留言 📝指正…...
framework.beans.factory.annotation.Autowired(required=true)}
将其它项目复制过来,启动后会报错 15:24:55.880 [main] ERROR o.s.b.SpringApplication - [reportFailure,843] - Application run failed org.springframework.beans.factory.UnsatisfiedDependencyException: Error creating bean with name containerDataHandleC…...
【应用笔记】使用 CW32 实现电池备份(VBAT)功能
前言 电池备份(VBAT)功能的实现方法,一般是使用 MCU 自带的 VBAT 引脚,通过在该引脚连接钮扣电池,当系统电源因故掉电时,保持 MCU 内部备份寄存器内容和 RTC 时间信息不会丢失。 本文档介绍了如何基于 C…...
探讨uniapp的navigator 页面跳转问题
navigator 页面跳转。该组件类似HTML中的<a>组件,但只能跳转本地页面。目标页面必须在pages.json中注册。 "tabBar": {"color": "#7A7E83","selectedColor": "#3cc51f","borderStyle": "bl…...
使用Epoll实现高效的多路I/O转接
文章目录 概述1. 理解Epoll机制2. Epoll的三个主要函数3. 基于Epoll实现多路I/O转接4. 总结 概述 在网络编程中,高效地处理大量并发连接是提升系统性能的关键。传统的多线程或多进程模型在这种情况下可能会导致资源消耗过大,而Epoll(事件驱动…...
流程挖掘in汽车丨宝马的流程效能提升实例
汽车行业在未来10年里,可能会面临比过去50年更多的变化。电动化、智能化、共享化和自动驾驶等方面的趋势可能给企业流程带来以下挑战: 供应链管理-电动化和智能化的发展可能导致供应链中的零部件和系统结构发生变化,企业需要重新评估和优化供…...
微信小程序实现当前页面更新上一个页面
日常项目中需要实现的一个价格脱敏功能:通过点击页面二中的查看完整信息 点击回退按钮实现页面一中的价格显露出来 通过查询了大量资料发现 大多数都是通过调用上一个接口的onload 或者onshow 实现视图更新 经测试后 发现 无法实现 只能更改数据 无法更新视图 实现…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
