算法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() 等)来计算每个组的汇总信息。以下是一个详细的例子…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...

什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...