网站 优化 分析,源码网站程序,wordpress qq邮箱订阅,wordpress仿微信公众号模板目录 题意
算法思路
过题图片
算法实现
代码解析
复杂度分析
题目链接
结论 题意
判断正整数 n 是不是快乐数。
快乐数定义#xff1a;
#xff08;1#xff09;每次将正整数替换为它每个位置上的数字的平方和。
#xff08;2#xff09;重复这个过程直到这个数…目录 题意
算法思路
过题图片
算法实现
代码解析
复杂度分析
题目链接
结论 题意
判断正整数 n 是不是快乐数。
快乐数定义
1每次将正整数替换为它每个位置上的数字的平方和。
2重复这个过程直到这个数变为 1也可能是无限循环但始终变不到 1。
3如果可以变为 1这个数就是快乐数。
示例 输入19
输出true
解释
1² 9² 82
8² 2² 68
6² 8² 100
1² 0² 0² 1
提示 1 n 2^31 -1
算法思路
这个问题的关键在于处理可能的无限循环。如果一个数最终会进入一个循环那么它肯定不是快乐数。因此我们可以使用哈希集合来记录在迭代过程中出现过的数。如果新生成的数已经在哈希集合中那么我们可以确定这个数不是快乐数因为它已经进入了循环。
过题图片 算法实现
以下是使用Java语言实现的算法
import java.util.Set;
import java.util.HashSet;class Solution {private int getNextNumber(int n) {int res 0;while (n 0) {int temp n % 10;res temp * temp;n n / 10;}return res;}public boolean isHappy(int n) {SetInteger record new HashSet();while (n ! 1 !record.contains(n)) {record.add(n);n getNextNumber(n);}return n 1;}
}
代码解析 getNextNumber 方法这个方法用于计算给定数的下一个数即每个位置上的数字的平方和。它通过不断取模和除法操作来实现。 isHappy 方法这是主要的算法实现。我们使用一个哈希集合 record 来记录出现过的数。在循环中我们不断计算下一个数并检查这个数是否已经在 record 中。如果已经在 record 中说明进入了循环返回 false。如果计算得到的数为1说明找到了快乐数返回 true。
复杂度分析 时间复杂度最坏情况下我们需要遍历所有可能的数直到找到1或者确定循环。在最坏情况下这个算法的时间复杂度是 O(k)其中 k 是快乐数序列的长度。对于非快乐数时间复杂度取决于循环的长度但在实际应用中这个循环通常不会太长。 空间复杂度我们使用了一个哈希集合来存储已经出现过的数因此空间复杂度是 O(k)其中 k 是不同数的数量。
题目链接
202. 快乐数 - 力扣LeetCode
结论
通过使用哈希集合来记录已经出现过的数我们可以有效地判断一个数是否为快乐数。这种方法简单而高效能够处理可能的无限循环问题。
写在最后 如果你觉得有帮助到你请给题解点个赞和收藏让更多的人看到呀~
也欢迎你关注我解锁更多图解 LeetCode一起玩转数据结构与算法
我是luckilyil我们下次见
