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

目录一、题目解析来自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说明陷入循环不是快乐数。理解比如n2的计算过程2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...这里进入了循环4之后又回到4。用快慢指针的话slow初始为2fast初始为bitSum(2)4第一次循环slow bitSum(2)4fast bitSum(bitSum(4))bitSum(16)37第二次循环slow bitSum(4)16fast 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则是快乐数否则不是 } }总结这道题的核心是把「数字平方和的循环计算」转化为「链表找环」问题用快慢指针高效判断。通过bitSum函数拆解每一位的操作再结合快慢指针的移动逻辑就能解决快乐数的判断~