LeetCode-Go 题解202. Happy Number 快乐数判定与哈希表判环实现详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 202. Happy Number 题解文档 为主体结合 LeetCode-Go 仓库中的 Go 源码与单元测试完整讲解快乐数Happy Number的定义、模拟运算流程、哈希表判环算法及其复杂度分析。读者学完后不仅能独立实现该题的 Go 解法还能掌握用哈希集合检测迭代过程是否陷入循环这一通用解题范式可迁移到其他判环类问题如链表中环、无限小数循环节等。题目描述编写一个算法来判断一个数字是否为快乐数happy number。快乐数定义为从任意正整数开始用其每一位数字的平方和替换该数并重复这一过程直到结果等于 1此后保持为 1或者陷入一个不包含 1 的无限循环。那些最终能够收敛到 1 的数就是快乐数。示例Input: 19 Output: true Explanation: 1² 9² 82 8² 2² 68 6² 8² 100 1² 0² 0² 1从 19 出发依次得到 82 → 68 → 100 → 1最终收敛到 1因此 19 是快乐数。题目理解把定义翻译成算法快乐数的定义本质上描述了一个迭代函数f(n) 每一位数字的平方之和从任意正整数n开始反复应用f会得到一条序列n, f(n), f(f(n)), ...。该序列的归宿只有两种可能序列到达 1 并停留在 1因为1² 1序列进入一个不包含 1 的循环永无止境。因此题目的判定逻辑可以简化为反复计算各位数字平方和若在某一步得到 1返回true若检测到之前出现过的数字即形成循环返回false。解题思路模拟迭代 哈希表判环官方文档给出的核心思路只有一句话——按照题意要求做即可Just follow the requirements of the problem statement但其背后的关键决策点是如何判定循环。因为该迭代过程是确定性的同样的输入必然得到同样的输出一旦某个数字在序列中第二次出现后续就必然重复之前走过的路径从而形成环。所以只需要用一个哈希表Go 中为map记录每一步已经访问过的数字在每一步生成新数字后检查它是否已经存在于记录中若存在 → 说明陷入循环且循环中不含 1返回false若新数字是 1 → 循环条件n ! 1不满足退出循环返回true。这种思路不需要任何数学推导或快慢指针是模拟 记忆化的最直观实现也正是本仓库题解所采用的方式。Go 源码实现解析仓库中的核心实现位于 202. Happy Number.go由两个函数组成package leetcode func isHappy(n int) bool { record : map[int]int{} for n ! 1 { record[n] n n getSquareOfDigits(n) for _, previous : range record { if n previous { return false } } } return true } func getSquareOfDigits(n int) int { squareOfDigits : 0 temporary : n for temporary ! 0 { remainder : temporary % 10 squareOfDigits remainder * remainder temporary / 10 } return squareOfDigits }主函数isHappy模拟与判环func isHappy(n int) bool { record : map[int]int{} for n ! 1 { record[n] n n getSquareOfDigits(n) for _, previous : range record { if n previous { return false } } } return true }执行流程逐行拆解初始化记录表record : map[int]int{}用于记录所有已访问过的数字循环终止条件for n ! 1——只要当前数字不是 1 就继续迭代一旦得到 1循环自然退出函数返回true记录当前数字record[n] n将本轮迭代的输入数字写入哈希表计算下一步n getSquareOfDigits(n)求出当前数字的各位平方和作为下一轮迭代的输入循环检测遍历record若新得到的n曾经出现过说明序列已经进入循环且永远无法到达 1立即返回false。需要说明的是map[int]int{}在这里仅当作集合使用value 值本身没有业务含义用map[int]bool或map[int]struct{}在语义上更贴近记录存在性读者可自行改写。辅助函数getSquareOfDigits拆位求平方和func getSquareOfDigits(n int) int { squareOfDigits : 0 temporary : n for temporary ! 0 { remainder : temporary % 10 squareOfDigits remainder * remainder temporary / 10 } return squareOfDigits }该函数采用取模 整除的标准拆位手法temporary % 10取出最低位数字累加该位数字的平方remainder * remaindertemporary / 10去掉最低位继续处理下一位直到temporary 0所有位处理完毕。例如对n 199² 81、1² 1累加得82与题目示例完全一致。注意此函数对n 0时循环体不执行、返回 0这在后续测试用例如输入 0 不会出现因为题目保证正整数中无影响。单元测试与验证仓库为本题提供了完整的表格驱动测试位于 202. Happy Number_test.go。测试覆盖了四种输入输入期望输出说明202false非快乐数会陷入循环19true题目官方示例2false经典的非快乐数序列为 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 43false非快乐数序列为 3 → 9 → 81 → 65 → 61 → 37 → ... 最终并入上述循环测试代码遵循本仓库统一的question202/para202/ans202结构组织用例运行时输出格式为fmt.Printf(------------------------Leetcode Problem 202------------------------\n) for _, q : range qs { _, p : q.ans202, q.para202 fmt.Printf(【input】:%v 【output】:%v\n, p, isHappy(p.one)) }执行验证方式任选其一# 方式一运行该题所在的 leetcode 包的全部测试 go test ./leetcode/0202.Happy-Number/... # 方式二仅运行本题测试 go test -run Test_Problem202 ./leetcode/0202.Happy-Number/... # 方式三仓库提供的覆盖率脚本生成 coverage.txt ./gotest.sh其中 gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对整个leetcode包批量生成覆盖率文件这也是本仓库宣称 100% 测试覆盖的验证入口。可以推断isHappy与getSquareOfDigits均被上述用例完全覆盖。复杂度分析时间复杂度O(L)其中L是序列进入循环或到达 1前的数字个数。虽然代码在每一轮迭代中遍历一次record当前实现为 O(1) 查找循环被写成了 O(已记录数) 的遍历实际运行时可简化为直接查哈希表但关键在于对任意正整数各位平方和的最大值增长是受限的。例如 4 位数最大为 9999其平方和为4 × 81 324可以证明数字一旦超过 243下一步的平方和必然回落。因此序列中可能出现的不同数字非常有限远小于 1000循环必然在有限步内被检测到整体可以视为常数级迭代次数。空间复杂度O(L)record哈希表存储了序列中出现的所有不同数字。若改用后面提到的快慢指针法空间复杂度可降为 O(1)。深入扩展数学性质与更优实现为什么非快乐数必然陷入循环这是本题判定循环即失败的数学依据。对任意k位数其各位平方和的最大值为81k。当k ≥ 4时81k 10^(k-1)例如 4 位数最大平方和 324 远小于最小的 4 位数 1000说明足够大的数经过一次变换后位数必然减少。因此序列中的数字被限制在一个有界范围内由鸽巢原理可知重复出现必然发生即必然进入循环。这就是循环中不含 1 即为非快乐数这一判据成立的根本原因。快慢指针Floyd 判环优化空间由于迭代函数是确定性的快乐数判定本质上是单链表是否带环问题把每个数字看作链表节点getSquareOfDigits就是next指针。因此可以直接套用 Floyd 快慢指针算法将空间复杂度从 O(L) 降为 O(1)func isHappyFloyd(n int) bool { slow, fast : n, n for { slow getSquareOfDigits(slow) fast getSquareOfDigits(getSquareOfDigits(fast)) if fast 1 { return true } if slow fast { return false } } }快指针每次走两步慢指针每次走一步若二者相遇说明有环非快乐数若快指针先到达 1 则为快乐数。已知循环入口 4从测试用例的轨迹可以看出所有非快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4这个 8 元循环。因此也存在一种极简判据迭代过程中一旦出现 4即可断定不是快乐数。不过该判据属于经验结论需要数学证明支撑作为工程实践中的快速剪枝技巧了解即可教学上仍推荐通用的哈希表或快慢指针方案。总结要点内容核心定义反复计算各位数字平方和最终收敛到 1 即为快乐数判定难点如何识别不包含 1 的循环仓库解法哈希表记录已访问数字重复出现即返回false辅助函数getSquareOfDigits用取模与整除拆位求平方和时间复杂度O(L)其中 L 为序列长度有界空间复杂度O(L)可用快慢指针优化到 O(1)测试依据202. Happy Number_test.go 覆盖 4 组用例本文以 关联题解文档 为骨架完整还原了题目定义、示例推演与 Go 实现并补充了源码逐行解析、测试验证、复杂度推导与判环优化。快乐数问题虽小却是理解确定性迭代 哈希记忆化思想的经典入门题这一模式在后续许多判环、去重类问题中都会反复出现值得牢固掌握。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：202. Happy Number 快乐数判定与哈希表判环实现详解
LeetCode-Go 题解202. Happy Number 快乐数判定与哈希表判环实现详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 202. Happy Number 题解文档 为主体结合 LeetCode-Go 仓库中的 Go 源码与单元测试完整讲解快乐数Happy Number的定义、模拟运算流程、哈希表判环算法及其复杂度分析。读者学完后不仅能独立实现该题的 Go 解法还能掌握用哈希集合检测迭代过程是否陷入循环这一通用解题范式可迁移到其他判环类问题如链表中环、无限小数循环节等。题目描述编写一个算法来判断一个数字是否为快乐数happy number。快乐数定义为从任意正整数开始用其每一位数字的平方和替换该数并重复这一过程直到结果等于 1此后保持为 1或者陷入一个不包含 1 的无限循环。那些最终能够收敛到 1 的数就是快乐数。示例Input: 19 Output: true Explanation: 1² 9² 82 8² 2² 68 6² 8² 100 1² 0² 0² 1从 19 出发依次得到 82 → 68 → 100 → 1最终收敛到 1因此 19 是快乐数。题目理解把定义翻译成算法快乐数的定义本质上描述了一个迭代函数f(n) 每一位数字的平方之和从任意正整数n开始反复应用f会得到一条序列n, f(n), f(f(n)), ...。该序列的归宿只有两种可能序列到达 1 并停留在 1因为1² 1序列进入一个不包含 1 的循环永无止境。因此题目的判定逻辑可以简化为反复计算各位数字平方和若在某一步得到 1返回true若检测到之前出现过的数字即形成循环返回false。解题思路模拟迭代 哈希表判环官方文档给出的核心思路只有一句话——按照题意要求做即可Just follow the requirements of the problem statement但其背后的关键决策点是如何判定循环。因为该迭代过程是确定性的同样的输入必然得到同样的输出一旦某个数字在序列中第二次出现后续就必然重复之前走过的路径从而形成环。所以只需要用一个哈希表Go 中为map记录每一步已经访问过的数字在每一步生成新数字后检查它是否已经存在于记录中若存在 → 说明陷入循环且循环中不含 1返回false若新数字是 1 → 循环条件n ! 1不满足退出循环返回true。这种思路不需要任何数学推导或快慢指针是模拟 记忆化的最直观实现也正是本仓库题解所采用的方式。Go 源码实现解析仓库中的核心实现位于 202. Happy Number.go由两个函数组成package leetcode func isHappy(n int) bool { record : map[int]int{} for n ! 1 { record[n] n n getSquareOfDigits(n) for _, previous : range record { if n previous { return false } } } return true } func getSquareOfDigits(n int) int { squareOfDigits : 0 temporary : n for temporary ! 0 { remainder : temporary % 10 squareOfDigits remainder * remainder temporary / 10 } return squareOfDigits }主函数isHappy模拟与判环func isHappy(n int) bool { record : map[int]int{} for n ! 1 { record[n] n n getSquareOfDigits(n) for _, previous : range record { if n previous { return false } } } return true }执行流程逐行拆解初始化记录表record : map[int]int{}用于记录所有已访问过的数字循环终止条件for n ! 1——只要当前数字不是 1 就继续迭代一旦得到 1循环自然退出函数返回true记录当前数字record[n] n将本轮迭代的输入数字写入哈希表计算下一步n getSquareOfDigits(n)求出当前数字的各位平方和作为下一轮迭代的输入循环检测遍历record若新得到的n曾经出现过说明序列已经进入循环且永远无法到达 1立即返回false。需要说明的是map[int]int{}在这里仅当作集合使用value 值本身没有业务含义用map[int]bool或map[int]struct{}在语义上更贴近记录存在性读者可自行改写。辅助函数getSquareOfDigits拆位求平方和func getSquareOfDigits(n int) int { squareOfDigits : 0 temporary : n for temporary ! 0 { remainder : temporary % 10 squareOfDigits remainder * remainder temporary / 10 } return squareOfDigits }该函数采用取模 整除的标准拆位手法temporary % 10取出最低位数字累加该位数字的平方remainder * remaindertemporary / 10去掉最低位继续处理下一位直到temporary 0所有位处理完毕。例如对n 199² 81、1² 1累加得82与题目示例完全一致。注意此函数对n 0时循环体不执行、返回 0这在后续测试用例如输入 0 不会出现因为题目保证正整数中无影响。单元测试与验证仓库为本题提供了完整的表格驱动测试位于 202. Happy Number_test.go。测试覆盖了四种输入输入期望输出说明202false非快乐数会陷入循环19true题目官方示例2false经典的非快乐数序列为 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 43false非快乐数序列为 3 → 9 → 81 → 65 → 61 → 37 → ... 最终并入上述循环测试代码遵循本仓库统一的question202/para202/ans202结构组织用例运行时输出格式为fmt.Printf(------------------------Leetcode Problem 202------------------------\n) for _, q : range qs { _, p : q.ans202, q.para202 fmt.Printf(【input】:%v 【output】:%v\n, p, isHappy(p.one)) }执行验证方式任选其一# 方式一运行该题所在的 leetcode 包的全部测试 go test ./leetcode/0202.Happy-Number/... # 方式二仅运行本题测试 go test -run Test_Problem202 ./leetcode/0202.Happy-Number/... # 方式三仓库提供的覆盖率脚本生成 coverage.txt ./gotest.sh其中 gotest.sh 使用go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对整个leetcode包批量生成覆盖率文件这也是本仓库宣称 100% 测试覆盖的验证入口。可以推断isHappy与getSquareOfDigits均被上述用例完全覆盖。复杂度分析时间复杂度O(L)其中L是序列进入循环或到达 1前的数字个数。虽然代码在每一轮迭代中遍历一次record当前实现为 O(1) 查找循环被写成了 O(已记录数) 的遍历实际运行时可简化为直接查哈希表但关键在于对任意正整数各位平方和的最大值增长是受限的。例如 4 位数最大为 9999其平方和为4 × 81 324可以证明数字一旦超过 243下一步的平方和必然回落。因此序列中可能出现的不同数字非常有限远小于 1000循环必然在有限步内被检测到整体可以视为常数级迭代次数。空间复杂度O(L)record哈希表存储了序列中出现的所有不同数字。若改用后面提到的快慢指针法空间复杂度可降为 O(1)。深入扩展数学性质与更优实现为什么非快乐数必然陷入循环这是本题判定循环即失败的数学依据。对任意k位数其各位平方和的最大值为81k。当k ≥ 4时81k 10^(k-1)例如 4 位数最大平方和 324 远小于最小的 4 位数 1000说明足够大的数经过一次变换后位数必然减少。因此序列中的数字被限制在一个有界范围内由鸽巢原理可知重复出现必然发生即必然进入循环。这就是循环中不含 1 即为非快乐数这一判据成立的根本原因。快慢指针Floyd 判环优化空间由于迭代函数是确定性的快乐数判定本质上是单链表是否带环问题把每个数字看作链表节点getSquareOfDigits就是next指针。因此可以直接套用 Floyd 快慢指针算法将空间复杂度从 O(L) 降为 O(1)func isHappyFloyd(n int) bool { slow, fast : n, n for { slow getSquareOfDigits(slow) fast getSquareOfDigits(getSquareOfDigits(fast)) if fast 1 { return true } if slow fast { return false } } }快指针每次走两步慢指针每次走一步若二者相遇说明有环非快乐数若快指针先到达 1 则为快乐数。已知循环入口 4从测试用例的轨迹可以看出所有非快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4这个 8 元循环。因此也存在一种极简判据迭代过程中一旦出现 4即可断定不是快乐数。不过该判据属于经验结论需要数学证明支撑作为工程实践中的快速剪枝技巧了解即可教学上仍推荐通用的哈希表或快慢指针方案。总结要点内容核心定义反复计算各位数字平方和最终收敛到 1 即为快乐数判定难点如何识别不包含 1 的循环仓库解法哈希表记录已访问数字重复出现即返回false辅助函数getSquareOfDigits用取模与整除拆位求平方和时间复杂度O(L)其中 L 为序列长度有界空间复杂度O(L)可用快慢指针优化到 O(1)测试依据202. Happy Number_test.go 覆盖 4 组用例本文以 关联题解文档 为骨架完整还原了题目定义、示例推演与 Go 实现并补充了源码逐行解析、测试验证、复杂度推导与判环优化。快乐数问题虽小却是理解确定性迭代 哈希记忆化思想的经典入门题这一模式在后续许多判环、去重类问题中都会反复出现值得牢固掌握。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考