【力扣】快乐数,哈希集合 + 快慢指针 + 数学

快乐数原题地址

方法一:哈希集合

定义函数 getNext(n) ,返回 n 的所有位的平方和。一直执行 n=getNext(n) ,最终只有 2 种可能:

  1. n 停留在 1 。
  2. 无限循环且不为 1 。

证明:情况 1 是存在的,如力扣的示例一:

接下来只需证明,反复执行 getNext 操作,最终一定会无限循环(停留在 1 可以理解为无限的 1→1 循环)。

分类讨论:

  1. n 的位数 ≤3 ,那么 getNext(n)<=getNext(999)=243 ,那么反复执行 getNext(n) ,执行 244 次以上,根据抽屉原理,一定会出现循环。
  2. n 的位数 >3 ,如 n 为 4 位数,执行 getNext(n) 后, n 的位数会减小,直到变为情况 1 。

所以,我们可以使用如下算法:反复执行 n=getNext(n) ,会出现下面 3 种情况:

  1. n=1 ,说明原来的 n 是快乐数。
  2. n 不在哈希表中,则把 n 插入哈希表。
  3. n 在哈希表中,且 n≠1 ,说明 n 已经进入循环,原来的 n 不是快乐数。
// 方法一:哈希集合
class Solution
{
public:bool isHappy(int n){unordered_set<int> hashtable;while (n != 1){// 若哈希表中没有 n ,就添加 n ,否则不是快乐数if (!hashtable.count(n)){hashtable.insert(n);}else{return false;}n = getNext(n);}return true;}
private:// 计算 n 的所有位的平方和int getNext(int n){int sum = 0;while (n){int digit = n % 10;n /= 10;sum += (digit * digit);}return sum;}
};

方法二:快慢指针(龟兔赛跑、弗洛伊德循环查找算法)

考虑到反复执行 n=getNext(n) ,一定会进入循环,参考判断链表是否带环的思路,定义 fast 和 slow , slow 每次执行 slow=getNext(slow) 一次, fast 每次执行 fast=getNext(fast) 两次,那么 slow 和 fast 最终一定会在循环内相遇。若相遇时 slow=fast=1 ,则 n 为快乐数,否则不是快乐数。

这是因为若链表带环,最终 fast 和 slow 一定会入环,且每次 fast 比 slow 多走一步, fast 和 slow 的距离缩短一步,最终距离一定会减为 0 ,两者相遇。

// 方法二:快慢指针法
class Solution
{
public:bool isHappy(int n){int slow = n;int fast = getNext(slow);while (slow != fast){// 慢指针一次走一步slow = getNext(slow);// 快指针一次走两步fast = getNext(getNext(fast));}return slow == 1;}
private:// 计算 n 的所有位的平方和int getNext(int n){int sum = 0;while (n){int digit = n % 10;n /= 10;sum += (digit * digit);}return sum;}
};

方法三:数学

根据方法一所述,反复执行 n=getNext(n) , n 一定会跌为三位数以下,且进入循环。使用硬编码穷举,最终的循环一定是 ...,4,16,37,58,89,145,42,20,4,... 或者 ...,1,1,...

所以只需要提前把循环中的数存储在哈希表中,反复执行 n=getNext(n) ,会出现 3 种情况:

  1. n 在哈希表中,说明已经进入循环,原来的 n 不是快乐数。
  2. n=1 ,说明原来的 n 是快乐数。
  3. n 不在哈希表中。
// 方法三:数学
class Solution
{
public:bool isHappy(int n){while (1){// 最终要么为 1 ,要么进入循环if (n == 1){return true;}else if (cycleMembers.count(n)){return false;}n = getNext(n);}}
private:// 计算 n 的所有位的平方和int getNext(int n){int sum = 0;while (n){int digit = n % 10;n /= 10;sum += (digit * digit);}return sum;}static unordered_set<int> cycleMembers;
};unordered_set<int> Solution::cycleMembers = { 4,16,37,58,89,145,42,20 };

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【C++基础入门】七、指针(定义和使用、所占内存空间、空指针和野指针、const关键字修饰指针、指针和数组、指针和函数)

七、指针 7.1 指针的基本概念 指针的作用&#xff1a; 可以通过指针间接访问内存 内存编号是从0开始记录的&#xff0c;一般用十六进制数字表示可以利用指针变量保存地址 7.2 指针变量的定义和使用 指针变量定义语法&#xff1a; 数据类型 * 变量名&#xff1b; 示例&…

深入Pandas:精通文本数据处理的20+技巧与应用实例【第68篇—python:文本数据处理】

文章目录 Pandas文本数据处理方法详解1. str/object类型转换2. 大小写转换3. 文本对齐4. 获取长度5. 出现次数6. 编码方向7. 字符串切片8. 字符串替换9. 字符串拆分10. 字符串连接11. 字符串匹配12. 去除空格13. 多条件过滤14. 字符串排序15. 字符串格式化16. 多列文本操作17. …

PHPExcel导出excel

PHPExcel下载地址 https://gitee.com/mirrors/phpexcelhttps://github.com/PHPOffice/PHPExcel 下载后目录结构 需要的文件如下图所示 将上面的PHPExcel文件夹和PHPExcel.php复制到你需要的地方 这是一个简单的示例代码 <?php$dir dirname(__FILE__); //require_once …

「Mybatis实战五」:Mybatis核心文件详解 - MyBatis常用配置environments、properties

一、MyBatis核心配置文件层级关系 ​ 本文代码在 Mybatis初体验&#xff1a;一小时从入门到运行你的第一个应用 所构建的基础代码结构之上&#xff0c;进行修改。 MyBatis 的配置文件包含了会深深影响 MyBatis 行为的设置和属性信息。 配置文档的顶层结构如下&#xff1a; 二…

Github 2024-02-08 开源项目日报 Top9

根据Github Trendings的统计&#xff0c;今日(2024-02-08统计)共有9个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Ruby项目1HTML项目1Python项目1Scala项目1PLpgSQL项目1Rust项目1NASL项目1C项目1TypeScript项目1非开发语言项目…

vue3:26—新的内置组件

目录 Teleport Suspense Teleport 什么是Teleport? Teleport 是一种能够将我们的组件html结构移动到指定位置的技术 当在元素中的css使用了filter滤镜属性的时候&#xff0c;会导致内部 fixed 元素定位发生错误&#xff0c;即不再相对 viewport 进行定位&#xff0c;而是相对…

Redis篇之redis是单线程

一、redis是单线程 Redis是单线程的&#xff0c;但是为什么还那么快&#xff1f;主要原因有下面3点原因&#xff1a; 1. Redis是纯内存操作&#xff0c;执行速度非常快。 2. 采用单线程&#xff0c;避免不必要的上下文切换可竞争条件&#xff0c;多线程还要考虑线程安全问题。 …

【Google Bard】免费生成图像——功能和使用方法详解

Google Bard 关于Bard 图片生成功能打开Bard通过Bard来生成图片Bard Vs Bing Vs Dall-EBard的生成结果Bing的生成结果Dall-E 的生成结果 总结 关于Bard 图片生成功能 Google在2月1日&#xff08;当地时间&#xff09;宣布&#xff0c;其对话型AI“Bard”新增了图像生成功能。 …

ICLR 2024 | Harvard FairSeg:第一个研究分割算法公平性的大型医疗分割数据集

近年来&#xff0c;人工智能模型的公平性问题受到了越来越多的关注&#xff0c;尤其是在医学领域&#xff0c;因为医学模型的公平性对人们的健康和生命至关重要。高质量的医学公平性数据集对促进公平学习研究非常必要。现有的医学公平性数据集都是针对分类任务的&#xff0c;而…

【Java】ArrayList和LinkedList的区别是什么

目录 1. 数据结构 2. 性能特点 3. 源码分析 4. 代码演示 5. 细节和使用场景 ArrayList 和 LinkedList 分别代表了两类不同的数据结构&#xff1a;动态数组和链表。它们都实现了 Java 的 List 接口&#xff0c;但是有着各自独特的特点和性能表现。 1. 数据结构 ArrayList…

泽攸科技ZEM系列台扫助力环境科研创新:可见光催化抗生素降解的探索

环境污染和能源短缺是当今人类社会面临的最严重威胁之一。为了克服这些问题&#xff0c;特别是在污水处理过程中&#xff0c;寻找新的技术来实现清洁、高效、经济的发展显得尤为重要。在各种工业废水中&#xff0c;抗生素的过量排放引起了广泛关注。抗生素的残留会污染土壤、水…

Openresty+Lua+Redis实现高性能缓存

一、背景 当我们的程序需要提供较高的并发访问时&#xff0c;往往需要在程序中引入缓存技术&#xff0c;通常都是使用Redis作为缓存&#xff0c;但是要再更进一步提升性能的话&#xff0c;就需要尽可能的减少请求的链路长度&#xff0c;比如可以将访问Redis缓存从Tomcat服务器…

部署 Spring 项目到 Linux 云服务器上

关于 Linux 服务器安装 JDK ,Mysql&#xff0c;配置安全组&#xff08;这些都是必要的&#xff09; 推荐看在 Linux 上搭建 Java Web 项目环境&#xff08;最简单的进行搭建&#xff09; 流程 1.上传Jar包到服务器 要想部署 Spring 项目&#xff0c;先要将 Spring 项目打成 J…

【51单片机】实现一个动静态数码管显示项目(超全详解&代码&图示)(5)

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机 系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY…

力扣优选算法100道——【模板】前缀和(一维)

【模板】前缀和_牛客题霸_牛客网 (nowcoder.com) 目录 &#x1f6a9;了解题意 &#x1f6a9;算法原理 &#x1f388;设定下标为1开始 &#x1f388;取值的范围 &#x1f6a9;实现代码 &#x1f6a9;了解题意 第一行的3和2&#xff0c;3代表行数&#xff0c;2代表q次查询(…

SegmentAnything官网demo使用vue+python实现

一、效果&准备工作 1.效果 没啥好说的&#xff0c;低质量复刻SAM官网 https://segment-anything.com/ 需要提一点&#xff1a;所有生成embedding和mask的操作都是python后端做的&#xff0c;计算mask不是onnxruntime-web实现的&#xff0c;前端只负责了把rle编码的mask解…

C#,栅栏油漆算法(Painting Fence Algorithm)的源代码

1 刷油漆问题 给定一个有n根柱子和k种颜色的围栏&#xff0c;找出油漆围栏的方法&#xff0c;使最多两个相邻的柱子具有相同的颜色。因为答案可以是大的&#xff0c;所以返回10^97的模。 计算结果&#xff1a; 2 栅栏油漆算法的源程序 using System; namespace Legalsoft.Tr…

[word] word中页眉怎么设置与上一节不同 #笔记#笔记#经验分享

word中页眉怎么设置与上一节不同 word中页眉怎么设置与上一节不同 1、首先打开一个文档&#xff0c;点击上方的命令栏&#xff0c;找到“页眉”指令。 2、点击编辑&#xff0c;输入页眉的文字&#xff0c;输入完成之后&#xff0c;会看到两页的页眉是一样的。 3、在“页面布局…

【从Python基础到深度学习】1. Python PyCharm安装及激活

前言&#xff1a; 为了帮助大家快速入门机器学习-深度学习&#xff0c;从今天起我将用100天的时间将大学本科期间的所学所想分享给大家&#xff0c;和大家共同进步。【从Python基础到深度学习】系列博客中我将从python基础开始通过知识和代码实践结合的方式进行知识的分享和记…

visual studio code could not establish connection to *: XHR failed

vscode远程连接服务器时&#xff0c;输入密码&#xff0c;又重新提示输入密码&#xff0c;就这样循环了好几次&#xff0c;然后会报上述的错误。由于我是window系统&#xff0c;我用cmd&#xff0c;然后ssh */你的IP地址/*发现可以远程到服务器上&#xff0c;但是通过Vscode就不…