算法1:双指针思想的运用(2)--C++
1.盛水最多的容器
题目链接:11. 盛最多水的容器 - 力扣(LeetCode)
题目解析:
在解析题目时,我们可以把最直接的方法先列举出来,然后再根据相应的算法原理,来进行优化
思路一:暴力求解
容器的容积计算方法:
假设两个指针i, j分别指向水槽班的两端,此时容器的宽度为j - i。由于容器的高度是有两个板子中的最短板来决定的,因此容积的公式为:
v = (j - i) * min(heght[i], height[j])
算法代码:
class Solution {
public:int maxArea(vector<int>& height) {int ret = 0;for (int i = 0; i < height.size() ; i++){for (int j = i + 1; j < height.size() ; j++){ret = max(ret, (j - i) * min(height[i], height[j]));}}return ret;}
};
这种解法可以解决部分用例但是是超时的,我们可不可以在暴力算法的基础上进行优化呢?
解法二:对撞指针
假设现在我们有两个指针left, right分别指向容器的左右两个端点,此时容器的容积:
v = (right - left) * min(heigth[left], height[right])
容器的左边界为 height[left] ,右边界height[right]
如果此时,我们来固定一个边界,改变另一个边界,水的容积就会有以下的变换形式:
- 容器的宽度一定在变小。
- 由于左边界较小,左边界就决定了水柱的高度。如果改变左边界,水柱的高度不会超过右边界,容积可能变高。
- 如果在这种情况下去移动右边界,宽度在减小,水柱的高度也不可能高过有边界,容积就一直在减小。
所以,左边界和其余边界的情况都可以直接舍去,这样就可以直接省去大量的枚举过程。
有了上面的理论基础,我们现在开始实现代码:
class Solution {
public:int maxArea(vector<int>& height) {int right = height.size() - 1, letf = 0, ret = 0;while (letf < right){ret = max(ret, (right - letf) * min(height[letf], height[right]));if (height[right] < height[letf])right--;elseletf++;}return ret;}
};
2.有效三角形的个数
题目链接: 611. 有效三角形的个数 - 力扣(LeetCode)
算法思路:
一.暴力枚举(超时)
三层for循环枚举出所有的三元数组,并判断满不满足三角形的成立条件。
这个十分的简单,我们这里就只展现一下代码:
class Solution {
public:int triangleNumber(vector<int>& nums) {int ret = 0;//1.现将整个数组进行排序sort(nums.begin(), nums.end());//固定最大值for (int right = nums.size() - 1; right >= 0; right--){//固定第二大的值for (int left = right - 1; left >= 0; left--){for (int i = left - 1; i >= 0; i--){if (nums[i] + nums[left] > nums[right])ret++;}}}return ret;}
};
接下来,我们来优化算法:
解法二:(排序 + 双指针)
1.现将数组进行排序
根据解法一中的优化思想,我们可以固定一个最长的边,然后在比这个边小的数组中找一个二元数组的和大于最大边的,由于数组有序,我们就可以在使用对撞指针来优化。
有了上面的理论基础,我们现在就来实现代码:
class Solution {
public:int triangleNumber(vector<int>& nums) {int ret = 0;sort(nums.begin(), nums.end());//固定最大值for (int i = nums.size() - 1; i >= 0; i--){int left = 0, right = i - 1;while (left < right){//nums此时是一个有序的数组,当遇到nums[left] + nums[right] > nums[i]时,//中间就会有right - left个元素符合条件if (nums[left] + nums[right] > nums[i]){ret += right - left;right--;}elseleft++;}}return ret;}
};
相关文章:

算法1:双指针思想的运用(2)--C++
1.盛水最多的容器 题目链接:11. 盛最多水的容器 - 力扣(LeetCode) 题目解析: 在解析题目时,我们可以把最直接的方法先列举出来,然后再根据相应的算法原理,来进行优化 思路一:暴力…...

L1415 【哈工大_操作系统】CPU调度策略一个实际的schedule函数
L2.7 CPU调度策略 1、调度的策略 周转时间:任务进入到任务结束(后台任务更关注)响应时间:操作发生到响应时(前台任务更关注)吞吐量:CPU完成的任务量 响应时间小 -> 切换次数多 -> 系统…...

免费版U盘数据恢复软件大揭秘,拯救你的重要数据
我们的生活和工作越来越离不开各种存储设备,其中优盘因其小巧便携、方便使用的特点,成为了我们存储和传输数据的重要工具之一。为了防止你像我一样会遇到数据丢失抓狂的情况,我分享几款u盘数据恢复软件免费版工具来即时补救。 1.福昕U盘数据…...

Pikachu-Unsafe FileUpload-客户端check
上传图片,点击查看页面的源码, 可以看到页面的文件名校验是放在前端的;而且也没有发起网络请求; 所以,可以通过直接修改前端代码,删除 checkFileExt(this.value) 这部分; 又或者先把文件名改成…...

【数据结构】什么是红黑树(Red Black Tree)?
🦄个人主页:修修修也 🎏所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录 📌红黑树的概念 📌红黑树的操作 🎏红黑树的插入操作 🎏红黑树的删除操作 结语 📌红黑树的概念 我们之前学过了…...
Xcode16适配
1.问题,第三方库报错信息如下: Declaration of sa_family_t must be imported from module Darwin.POSIX.sys.types._sa_family_t before it is required2.解答,在报错文件中导入以下头文件 #import <sys/_types/_sa_family_t.h>如有…...

Vue - 路由用法
前端路由就是URL中的hash与组件之间的对应关系。Vue Router是Vue的官方路由。 组成: VueRouter:路由器类,根据路由请求在路由视图中动态渲染选中的组件。<router-link>:请求链接组件,浏览器会解析成<a>。…...

SpringBoot框架下校园资料库的构建与优化
1系统概述 1.1 研究背景 如今互联网高速发展,网络遍布全球,通过互联网发布的消息能快而方便的传播到世界每个角落,并且互联网上能传播的信息也很广,比如文字、图片、声音、视频等。从而,这种种好处使得互联网成了信息传…...

vscode 连接云服务器(ubantu 20.04)
更改服务器系统 如果云服务器上的系统不是ubantu20.04的,可以进行更改: 登录云服务官网(这里以阿里云为例)点击控制台 点击服务器实例 点击更多操作、重置系统 点击重置为其他镜像、系统镜像:选择你要使用的系统镜像…...

【SpringBoot详细教程】-09-Redis详细教程以及SpringBoot整合Redis【持续更新】
🌲 Redis 简介 🌾 什么是Redis Redis 是C语言开发的一个开源高性能键值对的内存数据库,可以用来做数据库、缓存、消息中间件等场景,是一种NoSQL(not-only sql,非关系型数据库)的数据库 Redis是互联网技术领域使用最为广泛的存储中间件,它是「Remote DictionaryServic…...

排序算法之——归并排序,计数排序
文章目录 前言一、归并排序1. 归并排序的思想2. 归并排序时间复杂度及空间复杂度3. 归并排序代码实现1)递归版本2)非递归版本 二、计数排序1. 计数排序的思想2. 计数排序的时间复杂度及空间复杂度3. 计数排序代码实现 总结(排序算法稳定性&am…...

Linux中环境变量
基本概念 环境变量Environmental variables一般是指在操作系统中用来指定操作系统运行环境一些参数。 我们在编写C、C代码时候,在链接的时候从来不知道我们所链接的动态、静态库在哪里。但是还是照样可以链接成功。生成可执行程序。原因就是相关环境变量帮助编译器…...

163页PPT罗兰贝格品牌战略升级:华为案例启示与电器集团转型之路
罗兰贝格作为一家全球顶级的战略管理咨询公司,其品牌战略升级理念在多个行业中得到了广泛应用。以下将以华为案例为启示,探讨电器集团的转型之路,并融入罗兰贝格品牌战略升级的思想。 一、华为案例的启示 华为与罗兰贝格联合撰写的《数据存…...

系统设计,如何设计一个秒杀功能
需要解决的问题 瞬时流量的承接防止超卖预防黑产避免对正常服务的影响兜底方法 前端设计 利用 CDN 缓存静态资源,减轻服务器的压力在前端随机限流按钮防抖,防止用户重复点击 后端设计 Nginx 做统一接入,进行负载均衡与限流用 sentinel 等…...

Linux:进程入门(进程与程序的区别,进程的标识符,fork函数创建多进程)
往期文章:《Linux:深入了解冯诺依曼结构与操作系统》 Linux:深入理解冯诺依曼结构与操作系统-CSDN博客 目录 1. 概念 2. 描述进程 3. 深入理解进程的本质 4. 进程PID 4.1 指令获取PID 4.2 geipid函数获取PID 4.3 kill指令终止进程 …...

索尼MDR-M1:超宽频的音频盛宴,打造沉浸式音乐体验
在音乐的世界里,每一次技术的突破都意味着全新的听觉体验。 索尼,作为音频技术的先锋,再次以其最新力作——MDR-M1封闭式监听耳机,引领了音乐界的新潮流。 这款耳机以其超宽频播放和卓越的隔音性能,为音乐爱好者和专…...

【Linux】线程的概念
一、线程的概念 1.1 什么是线程 在一个程序里的一个执行路线就叫做线程,更准确的定义是:线程是“一个进程内部的控制序列”一切进程至少都有一个执行线程线程在进程内部运行,本质是在进程地址空间内运行在Linux系统中,在CPU眼中…...
centos7.9环境下mysql8数据库双机互备环境部署
为了实现mysql数据库的高可用性,数据库采用双机互备方式部署。双机互备能够避免单点故障造成的系统故障,由于两个节点都可以进行读写,同时也可以提高整个系统的数据读写并发性能。 1. 数据库安装 centos7安装mysql8 community 服务器IP:192.168.76.84 服务器IP:192.16…...

git 报错git: ‘remote-https‘ is not a git command. See ‘git --help‘.
报错内容 原因与解决方案 第一种情况:git路径错误 第一种很好解决,在环境变量中配置正确的git路径即可; 第二种情况 git缺少依赖 这个情况,网上提供了多种解决方案。但如果比较懒,可以直接把仓库地址的https改成ht…...
mysql学习教程,从入门到精通,SQL GROUP BY 子句(31)
1、SQL GROUP BY 子句 当然!在SQL中,GROUP BY 子句用于将结果集中的多个记录组合成一个摘要记录。通常,它用于结合聚合函数(如 COUNT(), SUM(), AVG(), MAX(), MIN() 等)来计算每个组的汇总信息。以下是一个详细的例子…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...