初识算法 · 双指针(2)
目录
前言:
盛最多水的容器
题目解析:
算法原理:
算法编写:
有效三角形的个数
题目解析:
算法原理:
算法编写:
前言:
本文介绍两个题目,盛最多水的容器和有效三角形的个数,对应的Leetcode的题目链接为:
11. 盛最多水的容器 - 力扣(LeetCode)
611. 有效三角形的个数 - 力扣(LeetCode)
介绍这两个题目,会从两角度进行介绍,暴力解法以及算法,整个题目的讲解分为三个部分,题目解析,算法原理,算法编写三个部分进行讲解。
现在就进入正题吧!
盛最多水的容器
题目解析:
题目:
题目实例:
该题目的要求是找到最大的值,值的求法为下标相减 * 两数中小的那个数,那么我们可以不管三七二十一,直接暴力,即将所有的值都给求出来,自然是两个循环就可以解决了,伪代码为:
for(...)
{//确定左边的边长
for(...)
{
//确定右边的边长
}
}
虽然说最后求值部分是一个等差数列的求和方式,但是不影响,最终的时间复杂度依旧是O(N^2)
对于为什么求值是*两数中较小的那个数,木桶效应相信大家都是听说过的:
即一个木桶盛水的容量不是取决于最长的木板,而是最短的那个木板,所以求值的时候是最小的那个值。
算法原理:
在算法原理部分,我们已经在上文了解了暴力解法,所以不再赘述暴力解法,这里是找两个数,保证下标相减 * 最小的那个数是最大值,那么找两个数,我们不妨使用双指针来解决。
容量大小 = 两数中的较小值 * 下标之差
我们不妨规定左指针从0开始,右指针从size - 1开始,如果我们从同向的方向进行判断,那么就会存在两变量,下标之差可能增大可能减少,较小值不确定,就会有4种情况,是比较难控制的,如果是我们定向的让右指针从右边开始,即数组的最末端,随着右指针往左或者是左指针往右,都是下标之差减少的过程,那么我们为了找最大值,需要保证的就是两个数之间的规则了。
谁小谁就移动,并且我们需要记录移动之前的容量大小,记录之后,需要比较移动之后的容量大小。我们取最大的即可。
算法编写:
class Solution
{
public:int maxArea(vector<int>& height){int left = 0, right = height.size() - 1;int ret = 0,ans = 0;while(right > left){ret = min(height[left],height[right]) * (right - left);ans = max(ret,ans);if(height[left] > height[right]) right--;else left++;}return ans;}
};
此时就完美通过了。
有效三角形的个数
题目解析:
题目:
题目示例:
通过示例,我们可以得出来一个结论是:下标不同数值相同的元素我们可以使用,即便组成的三角形是一样的。根据题目要求,我们首先得到的一个信息是,我们需要通过判断获取到的三个元素是否能构成三角形,那么根据初中的理论,三角形的充要条件是:任意两边之和大于第三边。
难道我们判断三角形的时候,就都要写三个条件吗?那是不是有点太麻烦了?这点先不管,题目中还有的提示是数组是非负的整数数组,也就是不会出现非整数和负数,我们返回值是能构成三角形的个数。题目要求不多,解析到这里已经差不多了。
算法原理:
还是那句话,遇事不决先暴力。
这道题的暴力解法是很简单的,我们只需要三个循环,一个循环找一条边即可:
for()
{for(){for(){//判断三角形是否成立}}
}
但是时间复杂度也是惊人的高,达到了O(N^3),一般leetcode上这种题,到最后几个样例的时候,O(N^3)一般都是会超时的。
所以我们需要另辟蹊径,那么就使用双指针算法,对于双指针来说,影响的是两个数,这是可是三个数,我们应该如何操作呢?
我们不妨借助单调性,如果借助单调性,我们碰见一组数,我们就要判断是否为三角形,这是否太麻烦了?那么有了单调性,比如a + b > c,随着指针往右边走,两个小的数都大于c了,其他的数还能不大于吗?到那个地步我们可以直接ans = 下标之差了,后面的肯定是符合条件的。那么c为最大边的所有三角形找到了,--即可。
算法编写:
class Solution
{
public:int triangleNumber(vector<int>& nums) {int ans = 0;sort(nums.begin(),nums.end());for(int i = nums.size() - 1; i >= 2 ;i--){int left = 0,right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]) ans += (right - left),right--;else left++; } }return ans;}
};
此时的时间复杂度为O(N^2),相对于O(N^3),是一个非常大的提升。
以上就是两道算法题目的详解。
感谢阅读!
相关文章:

初识算法 · 双指针(2)
目录 前言: 盛最多水的容器 题目解析: 算法原理: 算法编写: 有效三角形的个数 题目解析: 算法原理: 算法编写: 前言: 本文介绍两个题目,盛最多水的容器和有效三…...
React常见面试题目
React常见面试题目详解包括以下几个方面: 1. 对React的理解及特性 定义与用途:React是一个用于构建用户界面的JavaScript库,它遵循组件设计模式、声明式编程范式和函数式编程概念,使得前端应用程序更高效。 核心特性: …...

图解网络OSI模型与TCP/IP
一、OSI模型与TCP/IP 1、OSI模型 OSI/RM(Open System Interconnection,开放系统互联参考模型)是由ISO(国际标准组织)创建的一个有助于开放和理解计算机的通信模型,OSI七层参考模型作为一套规范的标准&…...

15分钟学 Python 第31天 :Web Scraping
Day 31:Web Scraping 1. Web Scraping 概述 Web Scraping(网页抓取)是一种自动提取网站数据的技术。它常用于从网页中收集信息,对数据进行分析和处理。无论是获取产品价格、市场调研,还是收集新闻信息,We…...

前端编程艺术(2)----CSS
目录 1.CSS 2.CSS引入 3.选择器 1.标签选择器 2.类选择器 3.id选择器 4.属性选择器 5.后代选择器 5.直接子元素选择器 6.伪类选择器 链接相关 动态伪类 结构化伪类 否定伪类 其他伪类 UI元素状态伪类 4.字体 1.font-family 2.font-size 3.font-style 4.fo…...
前端的全栈混合之路Meteor篇(二):RPC方法注册及调用
在Meteor 3.0中,RPC(远程过程调用)机制是实现前后端数据交互的重要特性。通过RPC,前端可以轻松调用后端方法(Methods)并获取数据,而后端的逻辑也可以同步或异步执行并返回结果。本文将详细介绍M…...

重学SpringBoot3-集成Redis(三)之注解缓存策略设置
更多SpringBoot3内容请关注我的专栏:《SpringBoot3》 期待您的点赞👍收藏⭐评论✍ 重学SpringBoot3-集成Redis(三)之注解缓存策略设置 1. 引入 Redis 依赖2. 配置 RedisCacheManager 及自定义过期策略2.1 示例代码:自定…...

【C++11】新特性
前言: C11 是C编程语言的一个重要版本,于2011年发布。它带来了数量可观的变化,包含约 140 个新特性,以及对 C03 标准中约600个缺陷的修正,更像是从 C98/03 中孕育出的新语言 列表初始化 C11 中的列表初始化࿰…...

【游戏模组】重返德军总部2009高清重置MOD,建模和材质全部重置,并且支持光追效果,游戏画质大提升
各位好,今天小编给大家带来一款新的高清重置MOD,本次高清重置的游戏叫《重返德军总部2009》2009年发布,我相信很多玩家已经玩过了,如果你还没有玩过我也可以和你简单介绍一下剧情,这款游戏故事背景接续在《重返德军总部…...

CGLib动态代理和JDK动态代理Demo、ASM技术尝鲜
本文主要介绍CGLib和JDK动态代理的使用,不对源码进行深入分析。代码可直接复制使用。 类型 机制 回调方式 适用场景 效率 JDK动态代理 委托机制。代理类和目标类都实现了同样的接口。InvocationHandler持有目标类。代理类委托InvocationHandler去调用目标类原…...

[C++]使用纯opencv部署yolov11-pose姿态估计onnx模型
【算法介绍】 使用纯OpenCV部署YOLOv11-Pose姿态估计ONNX模型是一项具有挑战性的任务,因为YOLOv11通常是用PyTorch等深度学习框架实现的,而OpenCV本身并不直接支持加载和运行PyTorch模型。然而,可以通过一些间接的方法来实现这一目标&#x…...
python you-get下载视频
You-Get是一个使用Python开发的命令行工具,用于下载网络上的音视频资源。你可以通过pip安装You-Get,具体操作如下: 打开命令行工具,输入pip install you-get,然后回车执行命令 You-Get还允许你指定下载的视频格式和质…...

SCUC博客摘录「 储能参与电能市场联合出清:SCUC和SCED模型应用于辅助服务调频市场(IEEE39节点系统)」2024年10月6日
2.1 SCUC模型在本方法中,首先利用SCUC模型确定机组出力计划和储能充放电计划。SCUC模型是电力系统经济调度的重要工具,通过优化发电机组出力计划和调度,实现电力系统的经济性和可靠性。在考虑储能的情况下,SCUC模型需要考虑储能的…...

Git分支-团队协作以及GitHub操作
Git分支操作 在版本控制过程中,同时推进多个任务> 程序员开发与开发主线并行,互不影响 分支底层也是指针的引用 hot-fix:相当于若在进行分支合并后程序出现了bug和卡顿等现象,通过热补丁来进行程序的更新,确保程序正常运行 常…...

力扣刷题 | 两数之和
目前主要分为三个专栏,后续还会添加: 专栏如下: C语言刷题解析 C语言系列文章 我的成长经历 感谢阅读! 初来乍到,如有错误请指出,感谢! 给定一个整数数组 nums 和…...

[C#]winform部署官方yolov11-obb旋转框检测的onnx模型
【官方框架地址】 https://github.com/ultralytics/ultralytics 【算法介绍】 Yolov11-obb(You Only Look Once version 8 with Oriented Bounding Boxes)是一种先进的对象检测算法,它在传统的Yolov3和Yolov4基础上进行了优化,加…...

【GC日志和OOM日志分析】JVM GC日志和OOM Dump文件分析
1 缘起 充电、充电、充电。 增加一些必备的知识,帮助后续使用。 2 配置JVM参数 为分析GC日志以及OOM相关信息,配置JVM参数,分为三个部分: (1)堆内存,包括年轻代、最大堆内存; &a…...

【电路】1.1 实际电路和电路模型
1.1 实际电路和电路模型 科学理论的研究对象是现实世界背后的抽象世界,如: 数学中的 ∞ \infty ∞,经典力学中“质点”的概念,牛顿运动定律(如惯性定律,如果一个物体不受外力情况下,一直保持匀…...

Vue - 打包部署
vscode找到NPM脚本,点击build。 目录下出现dist目录则表示安装成功。 安装Nginxnginx: download 目录用途conf配置文件目录html静态资源文件目录logs日志文件目录temp临时文件目录 将刚刚打包好的文件放到html目录下。 点击nginx.exe,用localhost:默认…...

spring揭秘25-springmvc03-其他组件(文件上传+拦截器+处理器适配器+异常统一处理)
文章目录 【README】【1】文件上传与MultipartResolver【1.1】使用MultipartResolver进行文件上传【1.2】springmvc处理multipart多部件请求流程【1.3】使用springmvc上传文件代码实现(springmvc6.10版本): 【2】Handler与HandlerAdaptor&…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...

C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...

JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...