算法每日双题精讲——双指针(快乐数,盛最多水的容器)

🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟

别再犹豫了!快来订阅我们的算法每日双题精讲专栏,一起踏上算法学习的精彩之旅吧!💪


目录

💯前言

💯快乐数

题目描述:

⭐解题思路:

🙋这个解题思路是怎么来的呢?  

代码实现(C++为例):

👀时间复杂度和空间复杂度

💯盛最多水的容器

题目描述:

⭐解题思路:

🙋这个解题思路是怎么来的呢?  

代码实现(C++为例):

👀时间复杂度和空间复杂度

💯总结


💯前言

在算法的奇妙世界里,双指针技巧宛如一把神奇的钥匙,能够开启许多难题的解决之门😎。

今日,就让我们一同深入探究两道借助双指针策略破解的经典题目:快乐数盛最多水的容器

📣由于俩道题目均为数组,这里的双指针算法指的是:利用数组下标代替指针

当我们遇到,数组分块,数组划分的问题时,可以考虑使用双指针法。 


💯快乐数


题目链接👉【力扣】

题目描述:

编写一个算法来判断一个数 n 是否为 “快乐数”。

“快乐数” 定义为

  1. 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,
  2. 然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。
  3. 如果这个过程结果为 1,那么这个数就是快乐数。

示例:

  • 输入:n = 19
  • 输出:true
  • 解释:
    • 1^2 + 9^2 = 82
    • 8^2 + 2^2 = 68
    • 6^2 + 8^2 = 100
    • 1^2 + 0^2 + 0^2 = 1

⭐解题思路:

我们可以使用双指针法来解决这个问题。定义一个快指针 fast 和一个慢指针 slow,初始时都指向数字 n。快指针每次计算下一个数时,会连续计算两次平方和,而慢指针每次只计算一次。通过不断重复这个过程,如果快指针等于 1,说明该数是快乐数;如果快指针等于慢指针且不等于 1,说明进入了循环,该数不是快乐数。

🙋这个解题思路是怎么来的呢?  

我们进行画图:

 

我们发现该题目像极了,环问题,因此我们的解题思路为快慢指针。 

代码实现(C++为例):
class Solution {
public:// 计算整数 n 各个数位上数字的平方和int sumN(int n) {int sum = 0;// 循环计算每个数位上数字的平方和while (n!= 0) {int t = n % 10;  // 取出 n 的最后一位数字sum += t * t;    // 将该数字的平方累加到 sum 中n = n / 10;      // 去掉 n 的最后一位数字}return sum;}// 判断整数 n 是否为快乐数bool isHappy(int n) {int slow = n;    // 慢指针,初始值为输入的整数 nint fast = sumN(n);  // 快指针,初始值为 n 的各个数位数字平方和// 使用快慢指针法检测是否存在循环while (slow!= fast) {slow = sumN(slow);   // 慢指针每次移动一步fast = sumN(sumN(fast));  // 快指针每次移动两步}return slow == 1;   // 如果慢指针等于 1,则说明 n 是快乐数}
};
👀时间复杂度和空间复杂度

时间复杂度:

  • 计算单个数字的数位平方和的时间复杂度为O(logn) ,因为数字的位数与 logn 成正比。
  •  isHappy 函数中,使用快慢指针法来判断是否为快乐数,在没有循环的情况下,时间复杂度取决于达到 1 的步数,最多不会超过O(logn) 。如果存在循环,时间复杂度也不会超过 O(logn),因为每次计算数位平方和都会使数字减小,最终会收敛到一个较小的范围。

空间复杂度:

  • 代码中只使用了有限的几个变量,不随输入规模增长,所以空间复杂度为O(1) 。


💯盛最多水的容器


题目链接👉【力扣】

题目描述:

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

示例:

  • 输入:height = [1,8,6,2,5,4,8,3,7]
  • 输出:49
  • 解释:图中垂直线代表输入数组 height。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49

⭐解题思路:

使用双指针法,一个指针指向数组的开头 left,一个指针指向数组的末尾 right。计算当前指针所构成容器的面积,面积等于两指针之间的距离乘以较小的高度 min(height[left], height[right])。然后根据高度大小移动指针,如果 height[left] < height[right],则将left 指针向右移动一位;否则将  right指针向左移动一位。重复这个过程,不断更新最大面积,直到 left right 指针相遇。

🙋这个解题思路是怎么来的呢?  

 

当宽度下降时,我们只要找高度比原来高的来计算新的体积 ,进行比较,找出最大的体积

 我们画图如下:

此时宽度最长

 left<right,我们让left++

right<left,我们让right--
以此类推,直到left==right

代码实现(C++为例):
class Solution {
public:// 计算给定高度数组中容器的最大盛水量int maxArea(vector<int>& height) {int left = 0;         // 左指针,初始指向数组首位置int right = height.size() - 1;  // 右指针,初始指向数组尾位置int V = (right - left) * min(height[left], height[right]);  // 初始盛水量while (left < right) {if (height[left] < height[right]) {left++;  // 如果左指针指向的高度较小,左指针右移} else {right--; // 如果右指针指向的高度较小,右指针左移}int newV = (right - left) * min(height[left], height[right]); // 新的盛水量V = max(V, newV); // 更新最大盛水量}return V;}
};
👀时间复杂度和空间复杂度

时间复杂度:

  • 由于只需要对数组进行一次遍历,所以时间复杂度为 O(n),其中 n 是数组的长度。

空间复杂度:

  • 代码中只使用了有限的几个变量,不随输入规模增长,所以空间复杂度为O(1) 。


💯总结

通过对快乐数和盛最多水的容器这两道题目的深入剖析,我们清晰地领略到了双指针算法在解决不同类型数组问题时所展现出的独特魅力与强大效能👏。它能够帮助我们巧妙地规避复杂的嵌套循环,以简洁高效的方式找到问题的答案。希望大家在今后的算法学习征程中,能够灵活运用双指针技巧,犹如掌握了一把锐利的武器,轻松攻克更多复杂的算法难题💪。 


我将持续在算法领域深耕细作,为大家带来更多精彩的算法知识讲解与问题解析。欢迎大家关注我

👉【A Charmer】

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

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

相关文章

【c++ gtest】使用谷歌提供的gtest和抖音豆包提供的AI大模型来对代码中的函数进行测试

【c gtest】使用谷歌提供的gtest和抖音豆包提供的AI大模型来对代码中的函数进行测试 下载谷歌提供的c测试库在VsCode中安装抖音AI大模型找到c项目文件夹&#xff0c;使用VsCode和VS进行双开生成gtest代码进行c单例测试 下载谷歌提供的c测试库 在谷歌浏览器搜索github gtest, 第…

数据库SQLite的使用

SQLite是一个C语言库&#xff0c;实现了一个小型、快速、独立、高可靠性、功能齐全的SQL数据库引擎。SQLite文件格式稳定、跨平台且向后兼容。SQLite源代码属于公共领域(public-domain)&#xff0c;任何人都可以免费将其用于任何目的。源码地址&#xff1a;https://github.com/…

【大咖云集,院士出席 | ACM独立出版】第四届大数据、人工智能与风险管理国际学术会议 (ICBAR 2024,11月15-17日)--冬季主会场

第四届大数据、人工智能与风险管理国际学术会议 (ICBAR 2024)--冬季主会场 2024 4th International Conference on Big Data, Artificial Intelligence and Risk Management 官方信息 会议官网&#xff1a;www.icbar.net 2024 4th International Conference on Big Data, Art…

图像算法之 OCR 识别算法:原理与应用场景

一、引言 在当今数字化时代&#xff0c;图像信息的处理和识别变得越来越重要。光学字符识别&#xff08;Optical Character Recognition&#xff0c;OCR&#xff09;算法作为一种能够将图像中的文字转换为可编辑文本的技术&#xff0c;正广泛应用于各个领域。从文档数字化到自…

SQLite的BLOB数据类型与C++二进制存储学习记录

一、BLOB数据类型简介 Blob&#xff08;Binary Large Object&#xff09;是一种用于存储二进制数据的数据类型&#xff0c;在数据库中常用于存储图片、音频和视频等大型&#xff08;大数据量&#xff09;的二进制数据[1-2]。需要注意的是&#xff0c;SQLite中BLOB类型的单对象最…

python基础——05函数

一、函数 1.1 函数定义 函数定义&#xff1a;实现特定功能的代码块 函数的作用&#xff1a; 简化代码提高代码重用性便于维护和修改可提高代码的可拓展性 函数三要素&#xff1a;功能、参数、返回值 函数定义的语法格式&#xff1a; 函数分类&#xff1a; 从定义的角度—…

[Redis] Redis哨兵机制

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏: &#x1f9ca; Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 &#x1f355; Collection与…

【Eclipse系列】eclipse安装与常规配置(含插件)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 一、下载与安装 二、常规设置 1.1.设置工作空间(workspace) 1.2.设置字体和字体大小 ​编辑 1.3.设置编码 1.4.去除验证(validation) 1.5.去除单词验证(spelli…

注册登录学生管理系统小项目

头文件 #ifndef _LOGINLINK_H_ #define _LOGINLINK_H_ #include<myhead.h> typedef struct {int id;char name[20];int age; }stu,*Pstu; typedef struct node {union{int len;stu data;};struct node *next; }node,*Pnode; int regist(); int login(); Pnode create()…

【在clion中构建python interpreter环境用于debug fastlio2】

在CLION中构建python interpreter环境 数据包在clion中构建python interpreter环境 数据包 数据包链接&#xff1a;fastlio2_ros2 在clion中构建python interpreter环境 通过clion中的remote development 通过SSH远程构建fastlio2 workspace 打开远程clion工作空间后&#x…

HTML+CSS基础【快速上手】

目录 一、HTML展示 1、HTML基础结构 2、认识元素属性 &#xff08;1&#xff09;元素属性理解 &#xff08;2&#xff09;实例 3、自结束标签和注释 &#xff08;1&#xff09;自结束标签 &#xff08;2&#xff09;注释 4、语义化标签 &#xff08;1&#xff09;语义…

6000字加图文 | 抓包带你深入了解网关到底起什么样的作用?不同网段通信的过程详解

不同网段通信的过程 不同网段就分两种了&#xff0c;同一个局域网下面&#xff0c;不同网段之间的通信&#xff0c;或者是从局域网去往互联网的通信&#xff0c;那么这个过程又是怎么样的呢&#xff1f; 还记得第二篇这个内容吗&#xff0c;访问者把数据交给网关&#xff0c;当…

Gpt4.0最新保姆级教程开通升级

如何使用 WildCard 服务注册 Claude3 随着 Claude3 的震撼发布&#xff0c;最强 AI 模型的桂冠已不再由 GPT-4 独揽。Claude3 推出了三个备受瞩目的模型&#xff1a;Claude 3 Haiku、Claude 3 Sonnet 以及 Claude 3 Opus&#xff0c;每个模型都展现了卓越的性能与特色。其中&a…

Python毕业设计选题:基于django+vue的网上购物系统的设计与实现

开发语言&#xff1a;Python框架&#xff1a;djangoPython版本&#xff1a;python3.7.7数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat11开发软件&#xff1a;PyCharm 系统展示 管理员登录 管理员功能界面 用户管理 商品类型管理 商品信息管理 系统管理 订单管理…

uniapp组件实现省市区三级联动选择

1.导入插件 先将uni-data-picker组件导入我们的HBuilder项目中&#xff0c;在DCloud插件市场搜索uni-data-picker 点击下载插件并导入到我们的项目中 2.组件调用 curLocation &#xff1a;获取到的当前位置&#xff08;省市区&#xff09; <uni-data-picker v-slot:defa…

关于Flutter空安全升级方案整理

前言 Flutter 从 2.0 版本开始支持空安全&#xff08;Null Safety&#xff09;。dart 版本为&#xff1a; environment:sdk: ">2.12.0 < 3.0.0"升级到空安全后&#xff0c;由于语法的变动&#xff0c;基本上整个工程&#xff0c;代码都爆红&#xff0c;这对项…

免费送源码:Java+ssm+MySQL ssm家电售后服务 计算机毕业设计原创定制

摘 要 信息化社会内需要与之针对性的信息获取途径&#xff0c;但是途径的扩展基本上为人们所努力的方向&#xff0c;由于站在的角度存在偏差&#xff0c;人们经常能够获得不同类型信息&#xff0c;这也是技术最为难以攻克的课题。针对家电售后服务等问题&#xff0c;对家电售后…

共享汽车管理新纪元:SpringBoot框架应用

4系统概要设计 4.1概述 本系统采用B/S结构(Browser/Server,浏览器/服务器结构)和基于Web服务两种模式&#xff0c;是一个适用于Internet环境下的模型结构。只要用户能连上Internet,便可以在任何时间、任何地点使用。系统工作原理图如图4-1所示&#xff1a; 图4-1系统工作原理…

yaml文件编写

Kubernetes 支持YAML和JSON格式管理资源 JSON 格式:主要用于 api 接口之间消息的传递 YAML 格式;用于配置和管理,YAML是一种简洁的非标记性语言,内容格式人性化容易读懂 一&#xff0c;yaml语法格式 1.1 基本语法规则 使用空格进行缩进&#xff08;不使用制表符&#xff0…

ssm071北京集联软件科技有限公司信息管理系统+jsp(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;北京集联软件科技有限公司信息管理系统 \ 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本信息…