当前位置: 首页 > news >正文

算法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.盛水最多的容器 题目链接&#xff1a;11. 盛最多水的容器 - 力扣&#xff08;LeetCode&#xff09; 题目解析&#xff1a; 在解析题目时&#xff0c;我们可以把最直接的方法先列举出来&#xff0c;然后再根据相应的算法原理&#xff0c;来进行优化 思路一&#xff1a;暴力…...

L1415 【哈工大_操作系统】CPU调度策略一个实际的schedule函数

L2.7 CPU调度策略 1、调度的策略 周转时间&#xff1a;任务进入到任务结束&#xff08;后台任务更关注&#xff09;响应时间&#xff1a;操作发生到响应时&#xff08;前台任务更关注&#xff09;吞吐量&#xff1a;CPU完成的任务量 响应时间小 -> 切换次数多 -> 系统…...

免费版U盘数据恢复软件大揭秘,拯救你的重要数据

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

Pikachu-Unsafe FileUpload-客户端check

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

【数据结构】什么是红黑树(Red Black Tree)?

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录 &#x1f4cc;红黑树的概念 &#x1f4cc;红黑树的操作 &#x1f38f;红黑树的插入操作 &#x1f38f;红黑树的删除操作 结语 &#x1f4cc;红黑树的概念 我们之前学过了…...

Xcode16适配

1.问题&#xff0c;第三方库报错信息如下&#xff1a; Declaration of sa_family_t must be imported from module Darwin.POSIX.sys.types._sa_family_t before it is required2.解答&#xff0c;在报错文件中导入以下头文件 #import <sys/_types/_sa_family_t.h>如有…...

Vue - 路由用法

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

SpringBoot框架下校园资料库的构建与优化

1系统概述 1.1 研究背景 如今互联网高速发展&#xff0c;网络遍布全球&#xff0c;通过互联网发布的消息能快而方便的传播到世界每个角落&#xff0c;并且互联网上能传播的信息也很广&#xff0c;比如文字、图片、声音、视频等。从而&#xff0c;这种种好处使得互联网成了信息传…...

vscode 连接云服务器(ubantu 20.04)

更改服务器系统 如果云服务器上的系统不是ubantu20.04的&#xff0c;可以进行更改&#xff1a; 登录云服务官网&#xff08;这里以阿里云为例&#xff09;点击控制台 点击服务器实例 点击更多操作、重置系统 点击重置为其他镜像、系统镜像&#xff1a;选择你要使用的系统镜像…...

【SpringBoot详细教程】-09-Redis详细教程以及SpringBoot整合Redis【持续更新】

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

排序算法之——归并排序,计数排序

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

Linux中环境变量

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

163页PPT罗兰贝格品牌战略升级:华为案例启示与电器集团转型之路

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

系统设计,如何设计一个秒杀功能

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

Linux:进程入门(进程与程序的区别,进程的标识符,fork函数创建多进程)

往期文章&#xff1a;《Linux&#xff1a;深入了解冯诺依曼结构与操作系统》 Linux&#xff1a;深入理解冯诺依曼结构与操作系统-CSDN博客 目录 1. 概念 2. 描述进程 3. 深入理解进程的本质 4. 进程PID 4.1 指令获取PID 4.2 geipid函数获取PID 4.3 kill指令终止进程 …...

索尼MDR-M1:超宽频的音频盛宴,打造沉浸式音乐体验

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

【Linux】线程的概念

一、线程的概念 1.1 什么是线程 在一个程序里的一个执行路线就叫做线程&#xff0c;更准确的定义是&#xff1a;线程是“一个进程内部的控制序列”一切进程至少都有一个执行线程线程在进程内部运行&#xff0c;本质是在进程地址空间内运行在Linux系统中&#xff0c;在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‘.

报错内容 原因与解决方案 第一种情况&#xff1a;git路径错误 第一种很好解决&#xff0c;在环境变量中配置正确的git路径即可&#xff1b; 第二种情况 git缺少依赖 这个情况&#xff0c;网上提供了多种解决方案。但如果比较懒&#xff0c;可以直接把仓库地址的https改成ht…...

mysql学习教程,从入门到精通,SQL GROUP BY 子句(31)

1、SQL GROUP BY 子句 当然&#xff01;在SQL中&#xff0c;GROUP BY 子句用于将结果集中的多个记录组合成一个摘要记录。通常&#xff0c;它用于结合聚合函数&#xff08;如 COUNT(), SUM(), AVG(), MAX(), MIN() 等&#xff09;来计算每个组的汇总信息。以下是一个详细的例子…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

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

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

UE5 学习系列(三)创建和移动物体

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

最新SpringBoot+SpringCloud+Nacos微服务框架分享

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

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

2025盘古石杯决赛【手机取证】

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

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...