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

3.快乐数专题学习笔记——双指针法在LeetCode 202题中的应用

news 2026/5/9 22:32:38

一、题目解析（来自LeetCode 202题）

快乐数的定义：

示例：

二、算法原理：快慢指针（类比链表找环）

核心思路：

理解：

三、代码实现（Java）

总结

今天在刷LeetCode的时候，遇到了第202题「快乐数」，结合联系链表是否有环这一个知识，我把学习过程整理成了这篇博客~

一、题目解析（来自LeetCode 202题）

OJ链接：https://leetcode.cn/problems/happy-number/

题目要求：编写一个算法判断一个数n是不是快乐数。

快乐数的定义：

对于一个正整数，每一次将它替换为它每个位置上的数字的平方和；然后重复这个过程直到这个数变为1，也可能是无限循环但始终变不到1。如果这个过程结果为1，那么这个数就是快乐数。

示例：

输入n = 19，输出true。解释：
输入n = 2，输出false（会进入无限循环，永远到不了1）。

二、算法原理：快慢指针（类比链表找环）

做这道题时，可以把快乐数的计算过程类比成链表的遍历，用「快慢指针」来判断是否陷入循环时的数字。

核心思路：

慢指针slow：每次只走一步（即计算一次「数字平方和」）。
快指针fast：每次走两步（即计算两次「数字平方和」）。
如果过程中fast遇到1，说明是快乐数；如果slow和fast相遇（且不是1），说明陷入循环，不是快乐数。

理解：

比如n=2的计算过程：2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...这里进入了循环（4之后又回到4）。用快慢指针的话：

slow初始为2，fast初始为bitSum(2)=4；
第一次循环：slow = bitSum(2)=4，fast = bitSum(bitSum(4))=bitSum(16)=37；
第二次循环：slow = bitSum(4)=16，fast = bitSum(bitSum(37))=bitSum(58)=89；
…… 直到slow和fast相遇（或fast到1）。

三、代码实现（Java）

我给的代码非常清晰，分为两个函数：bitSum计算数字的每一位平方和，isHappy用快慢指针判断是否为快乐数。

class Solution { // 返回n这个数每一位上的平方和 public int bitSum(int n) { int sum = 0; while (n != 0) { int t = n % 10; // 取最后一位 sum += t * t; // 平方累加 n /= 10; // 去掉最后一位 } return sum; } public boolean isHappy(int n) { int slow = n, fast = bitSum(n); // 慢指针从n开始，快指针先走一步 while (slow != fast) { // 相遇时退出循环 slow = bitSum(slow); // 慢指针走一步 fast = bitSum(bitSum(fast)); // 快指针走两步 } return slow == 1; // 相遇时是1则是快乐数，否则不是 } }