政府 网站模板/2022近期时事热点素材
双指针算法的妙用:提高代码效率的秘密(2)
前言:
小编在前几日讲述了有关双指针算法两道题目的讲解,今天小编继续进行有关双指针算法习题的讲解,老规矩,今天还是两道题目的讲解,希望各位在看完我这篇文章后有所收获,那么废话不多说,下面我们进入算法时间!
文章目录
- 双指针算法的妙用:提高代码效率的秘密(2)
- 1.快乐数
- 1.1.题目展示
- 1.2.题目解答
- 1.3.题目思路讲解
- 1.4.代码讲解
- 2.盛最多水的容器
- 2.1.题目展示
- 2.2.题目讲解
- 1.3.题目思路讲解
- 1.3.1.暴力解法
- 1.3.2.双指针算法
- 1.4.代码讲解
- 3.总结
正文:
1.快乐数
1.1.题目展示
老规矩,先来各位大家展示题目来源:202. 快乐数 - 力扣(LeetCode)
1.2.题目解答
我们先来观赏一下这个题目,这个题目读起来是很短的,它是想要我们去判断一个快乐数,并且给出了快乐数的定义,小编简单的概述一下:
- 定义一个正整数,每次让它等于它每个位(个,十,百等等)的数的平方和。
- 重复的进行上述平方和的操作,最后会出现两个结果:(1).无限循环直到变成1;(2).无限循环但是永远不到1.
- 如果最后一直循环的是1的话,我们就证明出这个数就是快乐数~
下面我们进入本题的思路讲解部分。
1.3.题目思路讲解
这个题目一拿到手可能会让部分读者朋友犯愁,其实这题就是纸老虎——看着吓人,其实不难,我们只要把思路捋顺就好,此时我们先看一个快乐数是如何得到的:
上面就是一个快乐数的得法,如果我们仅仅看这个例子,是总结不出来快乐数得到的方法,这个题目给出的第二个例子,就恰好让我们知道了快乐数一个隐藏的性质:
此时我们不难看出,如果这个数不是快乐数的话,会形成一个死循环,而不是单纯的无限循环,这是题目没有告诉我们的,如果题目告诉了我们这个性质,那么这个题目就是信手拈来,但可惜的是,当我们第一次见到这个题目,可能就会因为这个没告诉我们的隐藏性质而直接傻眼,这就告诉我们要巧用题目给出的例子,上面两个就是题目给出的例子,我们通过例子就可以推出这个隐藏性质,下面我就依靠这个性质来给各位讲述一下这个题目是如何解决的。
首先,各位要知道,其实快乐数也是形成了一个循环,只不过这个循环是以1进行的循环,非快乐数是会从开头就进入一个死循环的,最后还是会回到开头,可能听到这里,曾经看过我链表习题的读者朋友就想到了一个和这个题目类似的题:判断循环链表的题目,下面我放上那个博客的链接:单链表习题——快慢指针类习题详解!(2)-CSDN博客,这个题目和那个题目用到的是同一个思想,都需要采用快慢指针实现,我们都晓得快慢指针在一个循环的链中,总是可以相遇,如果相遇了就说明这个链子是循环的,此时我们就是要使用快慢指针来判断快乐数,如果快慢指针相遇的时候,此时的二者都是1的话,那么这个数就是快乐书;反之则不是快乐数,这便是这个题目的解题方法,下面小编展示这个题目的代码书写。
1.4.代码讲解
我们首先需要一个函数,它的作用就是来进行让一个数的每个位进行平方然后求和,在返回这个数,这是得到快乐数的其中一步,由于代码的难度不大,小编就不讲解了(如果有看不明白的读者朋友可以私信小编,小编会进行更详细的解答):
int getshort(int n){int sum = 0;while(n){int x = n % 10;sum+= x * x;n = n / 10;} return sum;}
之后我们进入主函数的书写,此时我们就和之前循环链表一样,先设置好快慢指针,刚开始让他们都是给定的n,之后我们就进入循环了,此时循环的条件是不太重要的,我就用1来代替了(因为之后我们肯定会判断出是否是快乐数,判断完后直接返回true或者false,循环会自动结束的),循环体内部,我们先让慢指针进行一次平方和,快指针进行两次平方和;之后我们判断二者是否相等,如果相等并且均等于1的话,那么我们返回true,证明此时为快乐数;如果相等但不等于1的话,那么就返回false,证明此时不为快乐数;如果不相等的话,继续循环,直到二者相等为止,此时我们就完成了主函数的书写下面小编给出这部分的代码:
bool isHappy(int n) {//先设置好快慢指针int _short = n,_long = n;while(1){_short = getshort(_short);_long = getshort(_long);_long = getshort(_long);if(_short == _long && _short== 1){return true;}else if(_short == _long && _short!= 1)return false;}}
以上便就是这个代码的所有,下面我给出完整代码并进入下个题目的讲述。
class Solution {
public:int getshort(int n){int sum = 0;while(n){int x = n % 10;sum+= x * x;n = n / 10;} return sum;}bool isHappy(int n) {//先设置好快慢指针int _short = n,_long = n;while(1){_short = getshort(_short);_long = getshort(_long);_long = getshort(_long);if(_short == _long && _short== 1){return true;}else if(_short == _long && _short!= 1)return false;}}
};
2.盛最多水的容器
2.1.题目展示
老规矩,小编给出本题目的来源:11. 盛最多水的容器 - 力扣(LeetCode)
2.2.题目讲解
首先,我先给各位打个强心剂,不要看这个题目难度是困难的各位就退缩了,其实这个题目的难度还是不算大,只要我们认真看完题目,并且懂了大概意思,这个题目就直接难度下降了,下面通过例题的图片来进行讲述:
通过题目的描述,我们容易知道这个题目是想让我们去求一块区间的最大体积,就拿上图所示,此时当高度为8和高度为7之间的区间体积应该是最大的,此时V=7 * (右 - 左)就可以求出来体积,这个题目就是想让我们去求一下任意两个区间的体积,求出其中的最大值,题目理解其实就是这么的容易,下面小编讲述一下这个题目的完成思路。
1.3.题目思路讲解
1.3.1.暴力解法
其实本题目一般读者拿到手的时候,第一个想到的往往就是采用暴力解法来进行做,此时题目会给我们一个数组的区间,此时我们仅需从第一个数开始进行一层循环,让它和它下一个的元素进行体积求解,直到把所有的体积求出来为止,虽然这么做是这个题目最简单的算法,但是,它的时间复杂度是非常大的,因为是套用两次循环,所以我们不难算出时间复杂度应该是:O(N^2),小编尝试过,这么做是无法在规定时间内完成这个题目的,所以这个暴力求解算法直接out掉,不过我们可以在暴力解法的基础上,进行算法的升级,下面小编讲述一个升级后的算法——双指针算法。
1.3.2.双指针算法
在讲述双指针算法之前,小编先简单的讲述一个小小的数学上的小技巧(关于单调性的),此时我们就拿例1的子数组来进行这个思路的讲解:
此时我们先计算这个小区间水的体积,我们就已2为左,8为右,不难发现此时的体积应该是2 * 3 = 6,此时我们在缩小区间,如果让右边的8往内走的话,此时的高度不变,长度变小,所以对应着的体积就会变小,所以说这么继续往后走是没有任何意义的,如果此时我们让2往里面走的话,此时的长度小了,高度大了,体积经过计算发现也大了,所以说,我们不拿看出一个小小的规律,如果此时我们先通过整个区间进行体积的计算,算出一个值后进行存储,然后比较左右两端的值,谁小谁就往里面走,直到左右相遇的时候便把一个数组便利完了,这其实就是这个题目的大致解法,可能我这么简单一说各位也不懂,下面我就通过图文的方式来介绍如何通过双指针进行这个题目的解法。
首先,我们准备一个数组,我就用例1的数组进行讲解,先定义好两个指针(cur和dest),一个指向左(cur),一个指向右(dest):
之后我们先记性两个位置的容器大小的计算,此时我们不难看出,高度是1,长度是:8,所以求得8;之后我们在进行两个头元素大小的比较,让小的继续里面走:
之后通过一个while循环,我们便可以得出一个相对区间的最大面积,最后我们把得出来的这些面积存储到一个vector容器里面,然后我们把元素拿出来进行比较,去到最大值,此就是盛水的最大量,以上就是思路讲述部分,下面进入代码实操部分。
1.4.代码讲解
首先,通过上述我讲述的思路不难看出,我们需要先右一个函数,这个函数是来进行比较两个数求出高,此时这个代码其实很容易去书写,我就不仔细解释了(如果不懂的私信问我,我会及时回复):
int getmin(int a,int b){if(a < b)return a;elsereturn b;}
之后,我们还需要一个函数,小编在最后一步说了,我们需要遍历完所有求出的体积,找到其中体积最大的,这个其实也好实现,找最大值函数想必各位之前在学习C语言的时候就写过(不仅仅局限于C语言,只要学校讲述了编程语言,这个算是一个很基础很基础的函数了),下面小编给出这个函数的书写:
int getmax(vector<int>& arr){int max = 0;for(int i = 0 ; i < arr.size() ; i++){if(arr[i] > max)max = arr[i];}return max;}
预备工作做完以后,下面我们就进入主函数的讲述部分,此时我们先设置好两个指针以及新开出一个容器用来存放体积,一个指针指向开始,一个指针指向最后,此时我们开始进行体积的求解,我们就要用到一个循环来进行求解,循环的条件自然是左要小于右,然后在循环体内,我们开始求出最小高度,之后把高度乘以两数之间的距离的值放入到容器内,然后比较左右,如果左大于右,那么让右往里面走,若左小于右,让左往里面走,此时不断循环,我们就可以求出每个区间的最大容量,之后我们直接返回所有容量的最大值,通过调用上面的返回最大值函数来进行最大值的返回,这么做的话主函数就可以写完了:
int maxArea(vector<int>& height) {size_t _left = 0,_right = height.size() - 1;vector<int> arr;while(_left < _right){int h = getmin(height[_left],height[_right]);arr.push_back(h * (_right - _left));if(height[_left] > height[_right])_right--;else _left++;}return getmax(arr);}
以上便就是代码部分的讲解,下面小编给出完整的代码:
class Solution {
public:int getmax(vector<int>& arr){int max = 0;for(int i = 0 ; i < arr.size() ; i++){if(arr[i] > max)max = arr[i];}return max;}int getmin(int a,int b){if(a < b)return a;elsereturn b;}int maxArea(vector<int>& height) {size_t _left = 0,_right = height.size() - 1;vector<int> arr;while(_left < _right){int h = getmin(height[_left],height[_right]);arr.push_back(h * (_right - _left));if(height[_left] > height[_right])_right--;else _left++;}return getmax(arr);}
};
3.总结
此时今天的两道题目到这里也就结束了,小编认为自己写的还是有些不太好,因为在写第二个题目的时候我忘记了相关的算法了,直到我重新看了一遍曾经的笔记后才想起来这个题目的解法,这个故事告诉我们要温故而知新,所以说第二个题目的讲解相对比较差一点,如果有错误,可以在评论区“批评”我,我还是很乐意接受各位的建议的,讲题的时光永远很短暂,那么各位大佬们,我们下一篇文章见啦!
相关文章:

双指针算法的妙用:提高代码效率的秘密(2)
双指针算法的妙用:提高代码效率的秘密(2) 前言: 小编在前几日讲述了有关双指针算法两道题目的讲解,今天小编继续进行有关双指针算法习题的讲解,老规矩,今天还是两道题目的讲解,希望…...

笔记--(网络3)、交换机、VLAN
交换机 交换机(Switch)意为“开关”是一种用于电(光)信号转发的网络设备。它可以为接入交换机的任意两个网络节点提供独享的电信号通路。最常见的交换机是以太网交换机。其他常见的还有电话语音交换机、光纤交换机等。 交换机的…...

昇思大模型平台打卡体验活动:基于MindSpore实现GPT1影评分类
如果你对MindSpore感兴趣,可以关注昇思MindSpore社区 大模型平台 平台说明 昇思大模型平台旨在为AI学习者和开发者提供在线学习的项目、模型、大模型体验和数据集的平台。我们也添加了各领域的经典数据集来帮助学习者解决AI学习过程中的一系列难题, 如…...

如何调整pdf的页面尺寸
用福昕阅读器打开pdf,进入打印页面,选择“属性”,在弹出的页面选择“高级” 选择你想调成的纸张尺寸,然后打印,打印出来的pdf就是调整尺寸后的pdf...

IDA*算法 Power Calculus————poj 3134
目录 闲聊 前言 DFS算法的无效搜索 BFS算法的空间浪费 IDDFS A*算法 IDA* Power Calculus 问题描述 输入 输出 问题分析 代码 闲聊 前几周在忙着数学竞赛,所以就没时间更新,高等数学,一生之敌,真不知道报名的时候我是怎么想…...

重磅!CoRL 2024顶刊会议 清华大学高阳研究组发布“基于大模型先验知识的强化学习”
正在德国举办的机器人研究领域的顶级学术会议CoRL 2024,清华大学交叉信息研究院高阳研究组发布重磅研究成果,提出“基于大模型先验知识的强化学习”框架(Reinforcement Learning with Foundation Priors) 来促进具身智能体在操作任务中的学习…...

泷羽sec学习打卡-Windows基础命令
声明 学习视频来自B站UP主 泷羽sec,如涉及侵权马上删除文章 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 关于windows的那些事儿-Base 一、Windows-BaseWindows有哪些版本呢,有什么区别呢?…...
RTC精度及校准
RTC精度偏差: RTC的基准时间和精度与石英晶体的频率相关,晶体的谐振频率取决于温度,因此RTC性能与温度相关,晶体的频率偏差是晶体正常频率的温度反转函数。 一、硬件方面: 1.使用高精度振荡器的RTC模块; …...

jQuery案例
以下是几个常见的 jQuery 示例,展示了它在不同场景下的应用: 1. 隐藏和显示元素 通过按钮点击隐藏和显示一个 <div> 元素。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><met…...

常见 HTTP 状态码分类和解释及服务端向前端返回响应时的最完整格式
目前开发的项目很大程度上是为明年的国产化做准备了,所以借这个机会把用了十年的自研系统全部重写,订立更严格的规范,本文记录一下返回格式及对应状态码。 常见 HTTP 状态码及解释 HTTP 状态码用于表示客户端请求的响应状态,它们…...

MySQL系列之如何在Linux只安装客户端
导览 前言Q:如何安装一个Linux环境下的MySQL客户端一、准备文件1. 确认Server版本2. 选择Client安装文件 二、下载并安装1. 下载1.1 寻找文件1.2 文件说明 2. 安装2.1 上传至Linux服务器2.2 执行安装 三、连接验证1. 确认远程授权2. 建立远程连接 结语精彩回放 前言…...

内核设备树,你真的了解吗?
在嵌入式系统和内核开发中,设备树(Device Tree, 简称 DT)扮演着至关重要的角色,帮助系统在启动时准确识别硬件配置并匹配合适的驱动程序。虽然设备树应用广泛,但其结构、工作机制及应用细节却不总是被深入理解。本文将…...

MySQL:客户端工具创建数据库
MySQL 是一个开源的关系型数据库管理系统(RDBMS),用于存储、管理和检索数据。MySQL是基于SQL语言的,它具有高效、可靠、易用的特点。 客户端工具 这个mysqld.exe就在计算机安装的数据可服务,启动之后,mys…...

Linux笔记之pandoc实现各种文档格式间的相互转换
Linux笔记之pandoc实现各种文档格式间的相互转换 code review! 文章目录 Linux笔记之pandoc实现各种文档格式间的相互转换1.安装 Pandoc2.Word转Markdown3.markdown转html4.Pandoc 支持的一些常见格式4.1.输入格式4.2.输出格式 1.安装 Pandoc sudo apt-get install pandoc # …...

【iOS】知乎日报第三周总结
【iOS】知乎日报第三周总结 文章目录 【iOS】知乎日报第三周总结前言评论区文字评论区的一个展开效果评论区数据的一个请求修改了主页获取数据的逻辑主页无限轮播图图片主色调的一个获取将一些拓展部分的内容写在分类里小结 前言 本周笔者因为金工实习整个项目进展比较慢&#…...

【p2p、分布式,区块链笔记 Torrent】WebTorrent的add和seed函数
在【p2p、分布式,区块链笔记 Torrent】WebTorrent的上传和下载界面的示例中,主要通过WebTorrent类的add和seed函数实现相关功能。这两个函数都返回一个Torrent类对象的实例。 seed函数 import createTorrent, { parseInput } from create-torrent // &…...

Redis穿透、击穿、雪崩
redis是一款常用的非关系型数据库,我们常用与作为数据缓存的组件。 接下来介绍一下面试中常被问到的三个概念以及简单的解决方法。 穿透 什么叫缓存穿透 缓冲穿透,是当有一个请求过来时,查询redis缓存不存在,又去查询数据库&…...

VBA高级应用30例应用3在Excel中的ListObject对象:插入行和列
《VBA高级应用30例》(版权10178985),是我推出的第十套教程,教程是专门针对高级学员在学习VBA过程中提高路途上的案例展开,这套教程案例与理论结合,紧贴“实战”,并做“战术总结”,以…...

2024系统架构师---上午综合题真题(重复考试知识难点)
1.感知层威胁 1)信息窃听:通过搭线或者电磁泄露造成数据隐私泄露;感知执行层主要由各种物理传感器组成,是整个物理信息系统中信息的来源。为了适应多变的环境,网络节点多布置在无人监管的环境中,因此容易被攻击者攻击,常见的针对感知执行层的攻击方式有; 2)感知破坏:…...

连接kafka消息队列报org.apache.kafka.clients.NetworkClient异常
启动kafka后,连接kafka消息队列报org.apache.kafka.clients.NetworkClient异常 could not be established. Broker may not be available. (org.apache.kafka.clients.NetworkClient) 检查kafka运行日志,报The broker is trying to join the wrong clu…...

淘宝商品评论API:代码界的“买家秀”大揭秘
在淘宝这个神奇的购物天堂里,商品评论就像是隐藏的宝藏,等待着我们去挖掘。想象一下,如果你的代码能够自动获取这些评论,那岂不是像拥有了一台时光机,可以穿梭在买家的购物体验之中?今天,我们就…...

RabbitMQ队列详细属性(重要)
RabbitMQ队列详细属性 1、队列的属性介绍1.1、Type:队列类型1.2、Name:队列名称1.3、Durability:声明队列是否持久化1.4、Auto delete: 是否自动删除1.5、Exclusive:1.6、Arguments:队列的其他属性…...

游戏服务器和普通服务器的区别
服务器,顾名思义,是提供服务的设备,在计算机领域,服务器是指具有网络功能的高性能计算机,用于存储、处理和传输数据,而游戏服务器则是专门为游戏提供服务的服务器,它需要具备更高的性能、更稳定…...

Java 中的 Supplier:让数据生成更灵活
文章目录 1. Supplier 基础:无参返回,懒加载的利器2. 与 Optional 配合,优雅地处理默认值3. 惰性初始化缓存:提升性能4. 用于随机数、时间戳等动态数据的生成5. 结合 Stream 实现动态数据流6. 与工厂模式结合,动态创建…...

轻松理解操作系统 - Linux的数据块是如何储存数据的?
python入门 C入门 Linux 由于其开源、比较稳定等特点统治了服务端领域。 也因此,学习Linux 系统相关知识在后端开发等岗位中变得越来越重要,甚至可以说是必不可少的。 因为它的广泛应用,所以在程序员的日常工作和面试中,它都是经…...

青藤深度参编的终端安全国家标准正式发布
近日,国家市场监督管理总局、国家标准化管理委员会发布中华人民共和国国家标准公告,由TC260(全国网络安全标准化技术委员会)归口,公安部第三研究所牵头的GB/T 29240-2024《网络安全技术 终端计算机通用安全技术规范》&…...

软考:去中心化的部署有什么特点
微服务架构被认为是去中心化的,因为它具有以下特点 模块化:微服务架构将应用程序拆分为一系列小型服务,每个服务都是独立的模块,易于维护和扩展 。这种模块化设计使得每个服务可以独立于其他服务运行,没有单一的控制中…...

L8.【LeetCode笔记】回文数
1.题目 https://leetcode.cn/problems/palindrome-number/description/ 给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。 回文数 是指正序(从左向右)和倒序(从右向左&…...

双版本android studio安装
安装双版本原因:不同的AS存在不兼容的情况,导致旧版本的项目在新项目下要各种修改,很讨厌,使用双版本,各使用各的就没有这样的问题了。 建议:先安装低版本安装版,再安装高版本免安装版…...

npm镜像的常用操作
查看当前配置的 npm 镜像 npm config get registry切换官方镜像 npm config set registry https://registry.npmjs.org/切换淘宝镜像(推荐) npm config set registry https://registry.npmmirror.com/切换腾讯云镜像 npm config set registry http://mirrors.cloud.tencent…...