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

【算法学习】-【双指针】-【快乐数】

LeetCode原题链接:202. 快乐数

下面是题目描述:

「快乐数」 定义为:

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

示例 1:
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2:
输入:n = 2
输出:false

提示:
1 <= n <= 231 - 1

1、题目分析
根据题目说明,给定的一个正整数,每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程,直到这个数变为 1,也可能是无限循环但始终变不到1;对于始终变不到1的情况,有没有可能不是循环但仍一直在变化呢?

答案是不可能。运用鸽巢原理可以证明这一点。那么下面是简单的证明过程:
先简单地说明一下鸽巢原理,也就抽屉原理,指的是:有n个鸽巢,n+1个鸽子,鸽子全部往巢中飞时,至少有一个鸽巢中鸽子的数量是大于1的
接下来开始证明。由题目所给的数据范围,我们可通过最大的一个数可以计算得到“鸽巢”的大小(范围), 231 - 1 = 2,147,483,647 ,经题目要求的计算方式计算一次可以得到一个数,260。那么任意一个符合题目数据范围的数只会在[1, 260]这个区间内变化,这个区间也就是“鸽巢”。也就是说,只要一个正整数比 231 - 1 小,它的变化只会在[1, 260]中,极端来看,一个数在变化了260次之后(把n个鸽巢填满),下一次变化也绝对会在这个范围中(让某个鸽巢中鸽子的数量大于1),因为那个数不管变成多少都一定比231 - 1 小。由此我们就无需担心一开始的那个问题。

2、解题思路
根据上面分析,给定的正整数要么是无限循环,要么最后变成1;再通过对两个示例中算出来的数进行 “连接”,会发现这个问题可以转换成为链表带环问题。如下图:
在这里插入图片描述
所以可以直接按解决链表带环的问题方法解决本题。唯一需要变化的就是快慢指针的定义。链表带环问题中,快指针一次走两步,慢指针一次走一步;在本题中,快指针一次按要求计算两次,慢指针按要求计算一次,最后判断两个指针是否相遇即可。

3、具体代码

class Solution {
public:int calculate(int num){int sum = 0;while(num){sum += pow(num % 10, 2);num /= 10;}return sum;}bool isHappy(int n) {int slow = calculate(n);int fast = calculate(calculate(n));while(slow != 1 && fast != 1){if(slow == fast){return false;}slow = calculate(slow);     //slow++;fast = calculate(calculate(fast));   //fast+=2;}return true;}
};

看完觉得有觉得帮助的话不妨点赞收藏鼓励一下,有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论,多多指点,谢谢朋友们!🌹🌹🌹

http://www.lryc.cn/news/182350.html

相关文章:

  • 【Java-LangChain:使用 ChatGPT API 搭建系统-6】处理输入-链式 Prompt Chaining Prompts
  • 从零手搓一个【消息队列】创建核心类, 数据库设计与实现
  • 14:00面试,14:06就出来了,这问的过于变态了。。。
  • url请求头信息
  • 【Oracle】Oracle系列之十六--数据库备份
  • uni-app:实现页面效果3
  • 计算机网络基础(一):网络系统概述、OSI七层模型、TCP/IP协议及数据传输
  • 互联网金融理财知识点简单总结
  • 微信小程序template界面模板导入
  • C/C++跨平台构建工具CMake-----在C++源码中读取CMakeLists.txt配置文件中的内容
  • 【MVP争夺战】python实现-附ChatGPT解析
  • 6 个最佳免费 Android 数据恢复软件
  • 数学建模Matlab之数据预处理方法
  • 如何保证Redis的HA高可用
  • 第一百六十三回 如何在任意位置显示PopupMenu
  • 采用python中的opencv2的库来运用机器视觉移动物体
  • 一、thymeleaf简介
  • 二分查找模版
  • idea清空缓存类
  • PAT(Basic Level) Practice(中文) 1015德才论
  • 接口自动化测试的概述及流程梳理~
  • 竞赛 机器视觉 opencv 深度学习 驾驶人脸疲劳检测系统 -python
  • 虚拟货币(也称为加密货币或数字货币)的运作
  • N. Number Reduction
  • Java集合面试题
  • Python 编程基础 | 第三章-数据类型 | 3.5、列表
  • Spring Cloud Zuul 基本原理
  • QT实现TCP服务器客户端的实现
  • 行为型设计模式——责任链模式
  • window安装压缩版postgresql