营销型网站有哪些app,jsp网站开发什么框架,网站怎么提高收录,wordpress 免费博客主题1.题目链接
202. 快乐数 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/happy-number/submissions/609206400/
2.题目描述
编写⼀个算法来判断⼀个数 n 是不是快乐数。 「快乐数」 定义为#xff1a; 对于⼀个正整数#xff0c;每⼀次将该数替换…1.题目链接
202. 快乐数 - 力扣LeetCodehttps://leetcode.cn/problems/happy-number/submissions/609206400/
2.题目描述
编写⼀个算法来判断⼀个数 n 是不是快乐数。 「快乐数」 定义为 对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平⽅和。 然后重复这个过程直到这个数变为 1也可能是⽆限循环但始终变不到 1 。 如果这个过程 结果为 1 那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true 不是则返回 false 。 ⽰例 1 输⼊ n 19 输出 true 解释 19 - 1 * 1 9 * 9 82 82 - 8 * 8 2 * 2 68 68 - 6 * 6 8 * 8 100 100 - 1 * 1 0 * 0 0 * 0 1 ⽰例 2 输⼊ n 2 输出 false 解释这⾥省去计算过程只列出转换后的数 2 - 4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - 4 - 16往后就不必再计算了因为出现了重复的数字最后结果肯定不会是 1 3.算法思路
该算法用于判断一个数是否为“快乐数”即通过反复计算各位平方和最终能得到 1 的数。其核心思想是 快慢指针法通过高效检测循环避免无限迭代具体步骤如下 1. 计算平方和的辅助函数 功能SunOfSquares(int n) 计算整数 n 每一位的平方和。 实现 通过循环取 n 的末位数字n % 10累加其平方值。 移除末位n / 10直到 n 变为 0。 示例 n 19 → 1² 9² 1 81 82。 2. 快慢指针检测循环 初始化 slow 初始化为 n每次走一步。 fast 初始化为 SunOfSquares(n)每次走两步。 循环条件 slow ! fast 时持续移动指针 slow 移动一步计算一次平方和。 fast 移动两步连续计算两次平方和。 终止条件当 slow 和 fast 相遇时说明存在循环或已到达 1。 3. 判断结果 若相遇时 slow 1说明最终收敛到 1是快乐数返回 true。 若相遇时 slow ! 1说明进入非 1 的循环返回 false。 算法关键点 快慢指针的优势 无需额外存储空间如哈希表空间复杂度为 O(1)。快指针的速度是慢指针的两倍确保在存在循环时快速相遇。 数学依据 根据弗洛伊德循环检测算法快慢指针必然在环内相遇。若结果为 1则后续所有平方和均为 1形成“自环”。 边界处理 当输入为 1 时直接跳过循环并返回 true保证正确性。 示例分析 输入n 19 过程 19 → 82 → 68 → 100 → 1 快慢指针在 1 处相遇返回 true。 输入n 2 过程 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4进入循环 快慢指针在 4 处相遇返回 false。 复杂度 时间复杂度O(n)其中 n 为到达循环或 1 的步数。快指针加速了循环检测。 空间复杂度O(1)仅使用固定空间存储指针。 4.代码实现
class Solution
{
public:// 定义函数 SumOfSquares 求 n 每一位数的平方和int SunOfSquares(int n){int sum 0;while(n){int temp n % 10;sum temp * temp;n n / 10;}return sum;}bool isHappy(int n) {int slow n, fast SunOfSquares(n);while(slow ! fast){slow SunOfSquares(slow);fast SunOfSquares(SunOfSquares(fast));}return slow 1;}
};
