双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动(2)

 

前言:

上篇我们讲解了双指针算法的含义以及相关题型讲解,本次则趁热打铁,通过进阶题目的分析与讲解,促使我们更深入和灵活的理解运用双指针算法。

 相关题目及讲解

一. 盛最多水的容器

题目链接:11. 盛最多水的容器 - 力扣(LeetCode)

题目分析:

1. 该题要求找到一个区间,数组内存储的元素即代表其对应的高度,宽度则为首尾元素下标之差

2. 根据木桶效应,两个板子一高一低,所能容纳水的高度应该为高度较低的那个

3. 因此,我们只需要逐个遍历相乘,求最大值即可

思路讲解:

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 枚举出所有可能出现的情况for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 计算容积,找出最⼤的那⼀个ret = max(ret, min(height[i], height[j]) * (j - i));}}return ret;}
};

 2. 对撞指针

由上述分析可知,装水容器的容积由高度和宽度确定。

我们不妨令左边界为left,右边界为right,假设left[height]<right[height],那么高度就会取左边界的高度,宽度即为right-left。

现在假设固定一个区间进行遍历,分以下几种情况讨论:

1)固定右边界,左边界向右遍历,宽度一定减小,高度的变化不确定,但一定不会大于右区间的高度,因此容积可能增大,也可能减小。

2)固定左区间,右区间向左遍历,宽度一定减小,高度只会变小或不变,因此容积一定减小

由此可见,固定高度较小区间的情况下容积大小的变化是确定的,因此我们只需固定高度较大的区间遍历即可,这样即可省去大量重复的计算比较。

代码实现:

class Solution {
public:int maxArea(vector<int>& height) {int ret=0;//最大容积int left=0,right=height.size()-1;//确定左右区间while(left<right){int v=min(height[left],height[right])*(right-left);ret=max(ret,v);//求最大容积if(height[left]<height[right]){left++;}else{right--;}}return ret;}
};

 二. 有效三角形的个数

题目链接:611. 有效三角形的个数 - 力扣(LeetCode)

题目分析:

1. 题目要求找出数组内可以组成三角形的种类个数,需注意,元素的大小可以重复,但是不能是数组内的同一个元素重复组合。

2. 判定方法:两小数之和大于大数,大数减次小数之差大于最小数

思路讲解:

判定方法中谈到了数大小的比较,因此我们可以先选择对数组进行排序

解法一:暴力解放(会超时)

排序后直接3个for循环进行遍历,此时时间复杂度已经来到了恐怖的n的三次方,基本上都会超时。

代码示例如下:  

class Solution {
public:int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 2. 从⼩到⼤枚举所有的三元组for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {// 当最⼩的两个边之和⼤于第三边的时候,统计答案if (nums[i] + nums[j] > nums[k])ret++;} }}return ret;}
};

解法二:双指针算法

在排序之后,我们可以首先固定一个最长边,假设其位置位于i处,则其坐区间[left,right]内的元素全部小于i处的元素,同时分以下几种情况讨论:

注意:此时区间内left处元素最小,right处元素最大!!!

1. nums[left]+nums[right]>nums[i],说明满足条件,且该区间内所有元素与right组合均可满足条件,此时right--,缩小区间继续判断

2. nums[left]+nums[right]<=nums[i],说明此时和较小,需要left++,寻找更大的元素进行判断

代码实现:

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());//排序int sum=0;//种类个数总和int n=nums.size();//总元素个数for(int i=n-1;i>=2;i--){int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){sum+=right-left;right--;}//区间内均满足,右区间向左遍历if(nums[left]+nums[right]<=nums[i]){left++;}//小于,左区间向右遍历}}return sum;}
};

小结:

本篇内容就到此为止啦!欢迎各位佬前来支持斧正,祝大家生活愉快,万事胜意!!!

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/464761.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

koa项目实战 == 实现注册登录鉴权

一. 项目的初始化 1 npm 初始化 npm init -y生成package.json文件: 记录项目的依赖 2 git 初始化 git init生成’.git’隐藏文件夹, git 的本地仓库 3 创建 ReadMe 文件 二. 搭建项目 1 安装 Koa 框架 npm install koa2 编写最基本的 app 创建src/main.js const Koa…

ONLYOFFICE 文档8.2更新评测:PDF 协作编辑、性能优化及更多新功能体验

文章目录 &#x1f340;引言&#x1f340;ONLYOFFICE 产品简介&#x1f340;功能与特点&#x1f340;体验与测评ONLYOFFICE 8.2&#x1f340;邀请用户使用&#x1f340; ONLYOFFICE 项目介绍&#x1f340;总结 &#x1f340;引言 在日常办公软件的选择中&#xff0c;WPS 和微软…

MATLAB下的四个模型的IMM例程(CV、CT左转、CT右转、CA四个模型),附下载链接

基于IMM算法的目标跟踪。利用卡尔曼滤波和多模型融合技术&#xff0c;能够在含噪声的环境中提高估计精度&#xff0c;带图像输出 文章目录 概述源代码运行结果代码结构与功能1. 初始化2. 仿真参数设置3. 模型参数设置4. 生成量测数据5. IMM算法初始化6. IMM迭代7. 绘图8. 辅助函…

Segmentation fault 问题解决

问题描述 执行有import torch代码的py 文件报Segmentation fault 原因分析&#xff1a; 查了网上说的几种可能性 import torch 时出现 “Segmentation fault” 错误&#xff0c;通常表示 PyTorch 的安装或配置存在问题 可能的原因 不兼容的库版本: PyTorch、CUDA 或其他依赖…

如何搭建汽车行业AI知识库:定义+好处+方法步骤

在汽车行业&#xff0c;大型车企面临着员工众多、价值链长、技术密集和知识传播难等挑战。如何通过有效的知识沉淀与应用&#xff0c;提升各部门协同效率&#xff0c;快速响应客户咨询&#xff0c;降低销售成本&#xff0c;并开启体系化、可持续性的知识管理建设&#xff0c;成…

QGIS:HCMGIS插件

插件GitHub地址&#xff1a;https://github.com/thangqd/HCMGIS。 以下对HCMGIS插件进行简单介绍&#xff0c;并演示如何进行地图数据下载。 插件简介 HCMGIS - Basemaps, Download OpenData, Batch Converter, VN-2000 Projections, and Field Calculation Utilities for QGI…

SpringBoot集成Shiro+Jwt+Redis

1. 概述 首先需要知道为什么使用 ShiroJwtRedis 进行登录认证和权限控制。 1. 为什么用Shiro&#xff1f; 主要用的是 shiro 的登录认证和权限控制功能。 Shiro 参见本栏目文章 &#x1f343;《Shiro实战》 2. 为什么用Jwt&#xff1f; Shiro 默认的 Session 机制来帮助实现…

jenkins 构建报错 Cannot run program “sh”

原因 在 windows 操作系统 jenkins 自动化部署的时候, 由于自动化构建的命令是 shell 执行的,而默认windows 从 path 路径拿到的 shell 没有 sh.exe &#xff0c;因此报错。 解决方法 前提是已经安装过 git WINR 输入cmd 打开命令行, 然后输入where git 获取 git 的路径, …

Springboot——对接支付宝实现扫码支付

文章目录 前言官方文档以及说明1、申请沙箱2、进入沙箱获取对应的关键信息3、拿到系统生成的公钥和密钥 注意事项创建springboot项目1、引入依赖2、配置连接参数3、创建配置类&#xff0c;用于接收这些参数4、中间类的定义(订单类)5、编写测试接口场景一、pc端请求后端后&#…

【云备份项目】json以及jsoncpp库的使用

目录 1.JSON 2.什么是 JSON&#xff1f; 3.JSON 发展史 4.为什么要使用 JSON&#xff1f; 5.JSON 的不足 6.JSON 应该如何存储&#xff1f; 7.什么时候会使用 JSON 7.1.定义接口 7.2.序列化 7.3.生成 Token 7.4.配置文件 8.JSON的语法规则 8.1.对象和数组 8.2.JS…

【C++篇】在秩序与混沌的交响乐中: STL之map容器的哲学探寻

文章目录 C map 容器详解&#xff1a;高效存储与快速查找前言第一章&#xff1a;C map 的概念1.1 map 的定义1.2 map 的特点 第二章&#xff1a;map 的构造方法2.1 常见构造函数2.1.1 示例&#xff1a;不同构造方法 2.2 相关文档 第三章&#xff1a;map 的常用操作3.1 插入操作…

HOT100_最大子数组和

class Solution {public int maxSubArray(int[] nums) {int[] dp new int[nums.length];int res nums[0];dp[0] nums[0];for(int i 1; i< nums.length; i){dp[i] Math.max(nums[i] ,dp[i-1] nums[i]);res Math.max(res, dp[i]);}return res;} }

contenteditable实现需要一个像文本域一样的可编辑框

我这里是因为左上和右下有一个固定的模板&#xff0c;所有用textarea有点不方便&#xff0c;查了下还有一个方法可以解决就是在需要编辑的元素上加上 :contenteditable"true" 完整代码如下&#xff0c;因为这个弹窗是两用的&#xff0c;所以用messageType做了一下判…

SpringBoot源码解析(一)

SpringBoot自动装配原理 SpringBootApplication注解 我们在使用SpringBoot时&#xff0c;通常使用的是SpringBootApplication这个注解&#xff0c;比如&#xff1a; 而这个注解的定义为下图&#xff0c;可以发现这个注解上有另外三个注解&#xff1a;SpringBootConfiguration…

WPF+MVVM案例实战与特效(二十四)- 粒子字体效果实现

文章目录 1、案例效果2、案例实现1、文件创建2.代码实现3、界面与功能代码3、总结1、案例效果 提示:这里可以添加本文要记录的大概内容: 2、案例实现 1、文件创建 打开 Wpf_Examples 项目,在 Views 文件夹下创建窗体界面 ParticleWindow.xaml,在 Models 文件夹下创建粒子…

js中怎么把excel和pdf文件转换成图片打包下载

index.html <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>文件转图片工具</title><!-- 本…

盘点 2024 十大免费/开源 WAF

WAF 是 Web Application Firewall 的缩写&#xff0c;也被称为 Web 应用防火墙。区别于传统防火墙&#xff0c;WAF 工作在应用层&#xff0c;对基于 HTTP/HTTPS 协议的 Web 系统有着更好的防护效果&#xff0c;使其免于受到黑客的攻击。 近几年经济增速开始放缓&#xff0c;科…

蓝牙资讯|苹果AirPods Pro 2推出听力测试、助听器和听力保护等功能

苹果推送iOS 18.1 系统版本更新&#xff0c;AirPods Pro 2 用户也在 iOS 18.1 中获得了强大的新功能。 运行固件 7B19 的 AirPods Pro 2 用户&#xff0c;搭配 iOS 18.1 系统的 iPhone&#xff0c;将获得三项强大的听力健康功能&#xff1a;听力测试、助听器和听力保护。 听力…

如何检查雷池社区版 WAF 是否安装成功?

容器运行状态检查&#xff1a; 使用命令行检查&#xff1a;打开终端&#xff0c;连接到安装雷池的服务器。运行 docker ps 命令&#xff0c;查看是否有与雷池相关的容器正在运行。 如果能看到类似 safeline-mgt、safeline-tengine 等相关容器&#xff0c;并且状态为 Up&#x…

【AI开源项目】Botpress - 开源智能聊天机器人平台及其部署方案

文章目录 Botpress 概述Botpress 的定位 Botpress 的主要特点1. OpenAI 集成2. 易于使用3. 定制和扩展性4. 多平台支持5. 集成和扩展 API6. 活跃的社区和详尽的文档 部署方案集成集成开发集成部署机器人示例开发工具代理本地开发先决条件从源代码构建 Botpress 如何解决常见问题…