Leetcode: NO.202 快乐数快慢指针

本文主要是介绍Leetcode: NO.202 快乐数快慢指针，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

题目链接：https://leetcode-cn.com/problems/happy-number

编写一个算法来判断一个数 n 是不是快乐数。

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解题记录

首先编写一个函数处理拆数字多平方加和处理

private static int tranNum(int n){int tmp = (int)Math.pow(n%10, 2);int quotient=n/10;while(quotient != 0){tmp += Math.pow(quotient%10, 2);quotient /= 10;}return tmp;
}

然后就是写个循环返回数字为1时放回true
问题在于何时终止循环返回false

运行测试发现，一旦出现如下数字，就会进入死循环
在这里插入图片描述
我们设置出现145直接跳出返回false

class Solution {public static boolean isHappy(int n){while( true ){n = tranNum(n);if (n==1) return true;if (n==145) return false;}}private static int tranNum(int n){int tmp = (int)Math.pow(n%10, 2);int quotient=n/10;while(quotient != 0){tmp += Math.pow(quotient%10, 2);quotient /= 10;}return tmp;}
}

在这里插入图片描述

进阶

上面解法有蒙的嫌疑，因为没有做数学求解
看了下题解，使用快慢指针可以判断是否进入死循环，因为快指针总能追上慢指针
在两个指针相等时判断是否等于1，即可分辨返回情况

class Solution {public static boolean isHappy(int n){int slow = n;do{n = tranNum(n);n = tranNum(n);slow = tranNum(slow);} while( n != slow );return slow==1;}private static int tranNum(int n){int tmp = (int)Math.pow(n%10, 2);int quotient=n/10;while(quotient != 0){tmp += Math.pow(quotient%10, 2);quotient /= 10;}return tmp;}
}