双指针算法的妙用:提高代码效率的秘密(2)

双指针算法的妙用:提高代码效率的秘密(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. 定义一个正整数,每次让它等于它每个位(个,十,百等等)的数的平方和。
  2. 重复的进行上述平方和的操作,最后会出现两个结果:(1).无限循环直到变成1;(2).无限循环但是永远不到1.
  3. 如果最后一直循环的是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.总结

此时今天的两道题目到这里也就结束了,小编认为自己写的还是有些不太好,因为在写第二个题目的时候我忘记了相关的算法了,直到我重新看了一遍曾经的笔记后才想起来这个题目的解法,这个故事告诉我们要温故而知新,所以说第二个题目的讲解相对比较差一点,如果有错误,可以在评论区“批评”我,我还是很乐意接受各位的建议的,讲题的时光永远很短暂,那么各位大佬们,我们下一篇文章见啦!
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/468282.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

浮动路由:实现出口线路的负载均衡冗余备份。

浮动路由 Tip&#xff1a;浮动路由指在多条默认路由基础上加入优先级参数&#xff0c;实现出口线路冗余备份。 ip routing-table //查看路由表命令 路由优先级参数&#xff1a;越小越优 本次实验测试两条默认路由&#xff0c;其中一条默认路由添加优先级参数&#xff0c;设置…

利用VMware workstation pro 17安装 Centos7虚拟机以及修改网卡名称

通过百度网盘分享的文件&#xff1a;安装虚拟机必备软件 链接&#xff1a;https://pan.baidu.com/s/1rbYhDh8x1hTzlSNihm49EA?pwdomxy 提取码&#xff1a;omxy 123网盘 https://www.123865.com/s/eXPrVv-UsKch 提取码:eNcy 先自行安装好VMware workstation pro 17 设置虚拟机…

如何在Linux中使用Cron定时执行SQL任务

文章目录 前言一、方案分析二、使用步骤1.准备脚本2.crontab脚本执行 踩坑 前言 演示数据需要每天更新监控数据&#xff0c;不想手动执行&#xff0c;想到以下解决方案 navicat 创建定时任务java服务定时执行linux crontab 定时执行sql脚本 一、方案分析 我选择了第三个方案…

SpringBoot技术在企业资产管理中的应用

4系统概要设计 4.1概述 系统设计原则 以技术先进、系统实用、结构合理、产品主流、低成本、低维护量作为基本建设原则&#xff0c;规划系统的整体构架. 先进性&#xff1a; 在产品设计上&#xff0c;整个系统软硬件设备的设计符合高新技术的潮流&#xff0c;媒体数字化、压缩、…

linux基础-完结(详讲补充)

linux基础-完结 一、Linux目录介绍 二、基础命令详细讲解 1. ls&#xff08;列出目录内容&#xff09; 2. cd&#xff08;更改目录&#xff09; 3. clear&#xff08;清除终端屏幕&#xff09; 4. pwd(显示你当前所在的目录) 5. vim(文本编辑器) 6. touch&#xff08;创…

ArcGIS软件之“计算面积几何”地图制作

目录 一、消防站的泰森多边形ex12二、人口调查的泰森多边形三、人口调查的泰森多边形属性设置四、计算面积几何,用于求密度五、求密度六、给“现有中学”属性 R1赋值七、“现有中学”设置多环缓存区 并为它赋值八、“土地使用”为不同的功能区赋值九、三个图层相交十、计算面积…

一、有限状态机

一、状态基类 在创建一个FSM的有限状态机的缩写脚本 例&#xff1a;比如枚举这个状态&#xff0c;现在不确定是给敌人还是玩家&#xff0c;那么就写一个枚举的基类 在这里先创建了三个抽象方法&#xff0c;进行状态的切换&#xff1b; 并且这是一个状态基类&#xff0c;不需要…

C++20 概念与约束(2)—— 初识概念与约束

1、概念 C20 中引入新的编译期关键字 concept 用于创建概念。个人认为将其翻译为“构思”更为贴切。直接使用时&#xff0c;它更像一个只能用于模板的布尔类型关键字。 而如果用于模板中&#xff0c;他会将模板类型先带入自身&#xff0c;当自身条件为 true 才会实例化模板&…

程序员会被AI取代吗?

时间&#xff1a;2024年 11月 10日 作者&#xff1a;小蒋聊技术 邮箱&#xff1a;wei_wei10163.com 微信&#xff1a;wei_wei10 音频&#xff1a;喜马拉雅 近年来&#xff0c;随着人工智能&#xff08;AI&#xff09;技术的发展&#xff0c;技术圈内关于“程序员会被AI取代…

2024 第五次周赛

A: 直接遍历即可 #include<bits/stdc.h> using namespace std;typedef long long ll; typedef pair<ll, ll>PII; const int N 2e6 10; const int MOD 998244353; const int INF 0X3F3F3F3F;int n, m; int main() {cin >> n;int cnt 0;for(int i 0; i …

十五、Linux线程(二)

4.线程的分离属性 通过属性设置线程的分离 1.线程属性类型&#xff1a; pthread_attr_t attr; 2.线程属性操作函数&#xff1a; &#xff08;1&#xff09;对线程属性变量的初始化 int pthread_attr_init(pthread_attr_t* attr); &#xff08;2&#xff09;设置线程分离属…

stm32 ADC实例解析(3)-多通道采集互相干扰的问题

文章目录 一、问题现象&#xff1a;二、原因分析&#xff1a;1、测量值不准问题分析&#xff1a;2、采样干扰问题分析 三、解决办法&#xff1a;1、硬件&#xff1a;&#xff08;1&#xff09;、电源供电&#xff08;2&#xff09;、引脚电容&#xff08;3&#xff09;、减少采…

定制ShardingSphere-Proxy镜像满足业务需求

Sharding官方提供的proxy镜像是基础版的&#xff0c;如果我们使用Sharding有以下任意需求&#xff0c;就需要添加额外的依赖到容器{path}/ext-lib目录下。 向Docker容器中添加jar包的方式多种多样&#xff0c;推荐采取使用Dockerfile的方式添加依赖。将原有的镜像作为基础镜像&…

【数据分享】1901-2023年我国省市县镇四级的逐年降水数据(免费获取/Shp/Excel格式)

之前我们分享过1901-2023年1km分辨率逐月降水栅格数据和Shp和Excel格式的省市县四级逐月降水数据&#xff0c;原始的逐月降水栅格数据来源于彭守璋学者在国家青藏高原科学数据中心平台上分享的数据&#xff01;基于逐月数据我们采用求年累计值的方法得到逐年降水栅格数据&#…

virtualBox部署minikube+istio

环境准备 virtualBox安装 直接官网下载后安装即可&#xff0c;网上也有详细教程。镜像使用的centos7。 链接&#xff08;不保证还可用&#xff09;&#xff1a;http://big.dxiazaicc.com/bigfile/100/virtualbox_v6.1.26_downcc.com.zip?auth_key1730185635-pWBtV8LynsxPD0-0-…

深入浅出WebSocket(实践聊天室demo)

文章目录 什么是WebSocket?WebSocket连接过程WebSocket与Http的区别重连机制完整代码使用方法心跳机制实现聊天室demo(基于Socket.io)参考文章、视频小广告~什么是WebSocket? WebSocket 是一种在单个TCP连接上进行全双工通信的协议(计算机网络应用层的协议) 在 WebSocket A…

[CKS] Audit Log Policy

最近准备花一周的时间准备CKS考试&#xff0c;在准备考试中发现有一个题目关于audit policy的题目。 What’s the audit policy 使用K8s Audit Policy&#xff0c;管理员可以定义哪些操作需要被审计&#xff0c;包括创建、删除、更新和查看集群中的资源。审计记录包括操作的时…

【C++】map和set的介绍及使用

前言&#xff1a; map和 set 是 C STL&#xff08;标准模板库&#xff09;中的两种非常重要的容器&#xff0c;它们基于一种叫做平衡二叉搜索树&#xff08;通常是红黑树&#xff09;的数据结构来实现。在 C 中&#xff0c;map 是一个键值对容器&#xff0c;set 只存储唯一的键…

ai外呼机器人的作用有哪些?

ai外呼机器人具有极高的工作效率。日拨打成千上万通不是问题&#xff0c;同时&#xff0c;机器人还可以快速筛选潜在客户&#xff0c;将更多精力集中在有价值的客户身上&#xff0c;进一步提升营销效果。183-3601-7550 ai外呼机器人的作用&#xff1a; 1、搭建系统&#xff0c…

QT版发送邮件程序

简单的TCP邮箱程序 **教学与实践目的&#xff1a;**学会网络邮件发送的程序设计技术。 1.SMTP协议 邮件传输协议包括 SMTP&#xff08;简单邮件传输协议&#xff0c;RFC821&#xff09;及其扩充协议 MIME&#xff1b; 邮件接收协议包括 POP3 和功能更强大的 IMAP 协议。 服务…