非循环数（Happy Number）完整解题指南：平方和变换、哈希集合与环检测的 LeetCode 实战

非循环数Happy Number完整解题指南平方和变换、哈希集合与环检测的 LeetCode 实战【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以仓库 hints/non-cyclical-number.md 的提示文档为主线系统讲解非循环数即 LeetCode 202 Happy Number快乐数的数学模型、环检测思路与多语言实现。读者将掌握各位数字平方和变换函数的写法、用哈希集合检测重复数字的经典套路以及如何用快慢指针把空间复杂度从O(logn)降到O(1)并能在 Python、Java、C、Go、Rust 等语言中直接落地。问题背景什么样的数才是非循环数非循环数这个命名取自 NeetCode 系列对 LeetCode 202Happy Number的别称核心定义如下对于一个正整数n反复执行将n替换为其每一位数字的平方和这一操作。若经过若干次变换后能够到达1则称该数为非循环数快乐数否则它将陷入一个永无1出现的循环即非循环判定失败。看一个典型的成功示例n 19该示例同样出现在仓库 cpp/0202-happy-number.cpp 的注释中1² 9² 82 8² 2² 68 6² 8² 100 1² 0² 0² 1 → 到达 1判定为 true再看一个失败示例n 22 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4从4开始会无限重复同一序列永远到不了1判定为false。题目要求返回布尔值true表示该数经过平方和变换链最终抵达1false表示它被困在某个不含1的循环里。核心数学模型平方和变换函数无论采用哪种解法第一步都是实现同一个变换函数把整数按十进制拆成单个数字对每个数字求平方后累加。这个函数在仓库各语言实现中通常命名为getNext、sumSquareDigits或sumOfSquare。以 python/0202-happy-number.py 为例def sumSquareDigits(self, n): output 0 while n: output (n % 10) ** 2 n n // 10 return output实现要点n % 10取出当前最低位数字n // 10去掉最低位循环直到n为 0由于只做整除和取模无需字符串转换性能最好go/0202-happy-number.go 给出了另一种先fmt.Sprint(n)转字符串再逐字符转数字的写法结果等价但常数开销更大实战中推荐取模写法单次变换的时间复杂度为O(logn)十进制数字个数约为log10(n)n的位数随其规模对数增长这与提示文档要求的O(logn)复杂度目标一致。为什么必须做环检测提示文档hints/non-cyclical-number.md 的 Hint 1明确指出模拟上述过程如果到达1返回true。但一旦某个数字被处理超过一次我们就会陷入循环cycle。这正是本题的关键陷阱平方和变换是一个确定性函数从任意起点出发后续序列完全由当前值决定。一旦某个值在序列中第二次出现那么它后面的所有值都会重复出现形成闭环——要么环中包含1快乐数要么环中不含1非快乐数。数学上可以证明这也是仓库中静态检测解法的依据十进制下平方和变换的序列只要不是快乐数最终必然进入唯一的一个循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4该循环在 javascript/0202-happy-number.js 中以cycles数组的形式被硬编码const cycles [4, 16, 37, 58, 89, 145, 42, 20];因此算法的本质可以归纳为一句话沿着变换链前进要么命中1要么检测到环某个值重复出现并返回false。剩余的问题只有一个——如何高效地检测到环。解法一哈希集合检测提示文档的标准解法提示文档Hint 2给出了最直观的落地方案使用哈希集合hash set检测某个数是否已被处理。每一步用变换函数更新n若结果为1返回true若n已存在于集合中返回false否则把n加入集合继续循环。typescript/0202-happy-number.ts 几乎逐字实现了该逻辑function isHappy(n: number): boolean { const visit new Set(); while (!visit.has(n)) { visit.add(n); n sumOfSquares(n); if (n 1) return true; } return false; }java/0202-happy-number.java 采用同样的思路并显式处理了边界值public boolean isHappy(int n) { if (n 1 || n -1) { return true; } SetInteger visit new HashSetInteger(); while (!visit.contains(n)) { visit.add(n); n sumOfSquare(n); if (n 1) return true; } return false; }go/0202-happy-number.go 用map[int]bool充当集合并把先判重再写入的循环条件用for {}无限循环 break表达语义等价for { if seen : alreadySeen[n]; seen { break } alreadySeen[n] true // ...计算平方和 total if total 1 { return true } n total total 0 } return false复杂度分析与提示文档推荐一致时间复杂度O(logn)每次变换O(logn)而数字值随变换快速收缩——例如任意 3 位数经一次变换后最大为9² × 3 243之后序列被限制在很小的数值范围内实际迭代次数是常数级空间复杂度O(logn)哈希集合最多存放变换链上出现过的不同数值。解法二快慢指针Floyd 环检测空间降到 O(1)哈希集合解法简单直观但需要O(logn)额外空间。提示文档给出的推荐复杂度为O(logn)时间 O(logn)空间即哈希解法即可达标不过若想进一步把空间压到O(1)仓库中的多语言实现展示了经典技巧——快慢指针。核心思路慢指针每次走一步变换一次快指针每次走两步变换两次。若序列中存在环快慢指针必然在环内相遇若序列直达1则快指针先到达1。相遇后只需检查当前位置是否为1即可判定。python/0202-happy-number.py 的实现class Solution: def isHappy(self, n: int) - bool: slow, fast n, self.sumSquareDigits(n) while slow ! fast: fast self.sumSquareDigits(fast) fast self.sumSquareDigits(fast) slow self.sumSquareDigits(slow) return True if fast 1 else Falsecpp/0202-happy-number.cpp 的注释给出了相同的思路说明并在循环条件中额外加入fast ! 1提前退出class Solution { public: bool isHappy(int n) { int slow n; int fast getNext(n); while (slow ! fast fast ! 1) { slow getNext(slow); fast getNext(getNext(fast)); } return fast 1; } private: int getNext(int n) { int sum 0; while (n 0) { int digit n % 10; n / 10; sum pow(digit, 2); } return sum; } };c/0202-happy-number.c 与 kotlin/0202-happy-number.kt 的结构几乎一致均以while (slow ! fast)为外层循环、快指针内部嵌套两次变换class Solution { fun isHappy(n: Int): Boolean { var slow n var fast sumSquareDigits(n) while (slow ! fast) { fast sumSquareDigits(sumSquareDigits(fast)) slow sumSquareDigits(slow) } return fast 1 } // ... }复杂度分析时间仍为O(logn)快慢指针只是把常数放大到约 2 倍数量级不变空间降为O(1)因为只用了两个整数变量不依赖任何集合。解法三数学常数优化利用唯一循环由于非快乐数最终必然落入唯一循环4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4可以把环的信息直接编码进代码省去运行期建集合的开销时间与空间均为O(logn)与O(1)。变体 A静态哈希集合。javascript/0202-happy-number.js 把已知循环的所有值预置进Set循环条件只需判断n 1 || seen.has(n)var isHappy (n) { const cycles [4, 16, 37, 58, 89, 145, 42, 20]; const seen new Set(cycles); while (!(n 1 || seen.has(n))) { n getNext(n); } return n 1; };变体 B只判断n 4。因为环上任何一个节点都通向4所以只要序列中出现4即可判定为非快乐数。rust/0202-happy-number.rs 用 Rust 的match精准表达了这个判定impl Solution { pub fn is_happy(mut n: i32) - bool { loop { let mut s 0; while n 0 { s (n % 10).pow(2); n / 10; } match s { 1 | 4 break s 1, _ n s, } } } }这一变体同样出现在 javascript/0202-happy-number.js 的第三种实现中const hasCycle () n 1 || n 4;。注意这两种变体依赖非快乐数必入 4-循环的数学结论属于领域知识优化在面试中建议先给出解法一再补充说明该优化并指出其成立的前提是十进制平方和变换的这一性质。三种解法复杂度总览解法检测环的手段时间复杂度空间复杂度仓库代表实现哈希集合运行期动态记录已见值O(logn)O(logn)typescript/0202-happy-number.ts、java/0202-happy-number.java、go/0202-happy-number.go快慢指针Floyd 龟兔赛跑相遇即环O(logn)O(1)python/0202-happy-number.py、cpp/0202-happy-number.cpp、c/0202-happy-number.c、kotlin/0202-happy-number.kt数学常数硬编码唯一循环 / 判定n 4O(logn)O(1)rust/0202-happy-number.rs、javascript/0202-happy-number.js选择建议提示文档要求的不劣于O(logn)时间 O(logn)空间由解法一即可满足追求极致空间或作为进阶展示时使用解法二解法三适合在确认数学结论后作为常数级优化补充讲解。多语言实现速查本仓库在 12 种语言中均提供了本题实现文件名统一为0202-happy-number便于对照学习Python快慢指针Java哈希集合 边界值处理C快慢指针 powC快慢指针Gomap判重 字符串拆分写法TypeScript哈希集合JavaScript四种解法齐备含静态环集合与n 4判定Kotlin快慢指针Rustmatch匹配1 | 4O(1)空间此外仓库还包含 csharp、ruby、swift、dart、scala 等语言目录下的同名实现对照阅读时建议重点关注两点其一getNext/sumSquareDigits在不同语言中取模拆位的写法差异n // 10vsMath.floor(n / 10)vsn / 10整数除法语义各不相同其二环检测的数据结构选型Set、HashSet、map[int]bool在各自语言中的惯用法这两点正是把同一算法移植到多语言时的常见踩坑点。总结非循环数快乐数题目本身逻辑简单但它是确定性变换 环检测这类问题的典型代表与链表判环、函数迭代找周期等问题共享同一套思维模型。完整解题链路为先写出O(logn)的平方和变换函数再用哈希集合检测重复对应提示文档 Hint 1/2 的标准答案进阶时用快慢指针把空间降到O(1)最后可以基于非快乐数必入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4唯一循环的数学结论做常数级优化。掌握了这条链路你就同时具备了快乐数问题本身、哈希判重、Floyd 环检测三类面试高频考点的实战能力。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考