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

广州网站建设app开发python网站开发框架

news 2025/9/18 12:46:28

广州网站建设app开发,python网站开发框架,wordpress二维码,站内营销推广方案目录题意算法思路过题图片算法实现代码解析复杂度分析题目链接结论题意判断正整数 n 是不是快乐数。快乐数定义： （1）每次将正整数替换为它每个位置上的数字的平方和。 （2）重复这个过程直到这个数…

题意

算法思路

过题图片

算法实现

代码解析

复杂度分析

题目链接

结论

题意

判断正整数 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) {Set<Integer> 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 是不同数的数量。