力扣-202. 快乐数解析-弗洛伊德循环查找算法

本文主要是介绍力扣-202. 快乐数解析-弗洛伊德循环查找算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

 

public static void Happy(int n) {int sum = 0;int digit = 0;for (int i = 0; i < 20; i++) {while (n != 0) {digit = n%10;sum += digit*digit;n/=10;}System.out.print(sum + " ");n = sum;sum = 0;}}

使用代码测试一下每一代数字 

n = 2 :
4 16 37 58 89 145 42 20 4 16 37 58 89 145 42 20 4 16 37 58 
n = 3 :
9 81 65 61 37 58 89 145 42 20 4 16 37 58 89 145 42 20 4 16 
n = 4 :
16 37 58 89 145 42 20 4 16 37 58 89 145 42 20 4 16 37 58 89 
n = 5 :
25 29 85 89 145 42 20 4 16 37 58 89 145 42 20 4 16 37 58 89 
n = 6 :
36 45 41 17 50 25 29 85 89 145 42 20 4 16 37 58 89 145 42 20 
n = 7 :
49 97 130 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

可以发现

归纳一下这些简单数字就可以发现，对于任意一个非快乐数，最终会进入重复循环， ···不难发现，4即之后的结果就是新一轮循环。

那么我的第一个做法是检测4出现的次数 如果4出现次数超过两次, 那么就不是快乐数

{int sum = 0;int n1 = n;int count = 0;for (int i = 0;  ; i++) {while (true) {int a = n%10;sum += a*a;n /= 10;if (n == 0){break;}}if (sum==4){count++;}if (sum==1){return true;}if (count==2){return false;}n = sum;sum=0;}}

感觉不太行 

想了一想 其实这道题为弗洛伊德查找算法提供了很好的条件

弗洛伊德查找算法原理见此处链接

代码如下:

{//弗洛伊德循环查找算法public static boolean isHappy(int n) {int slow = n;int fast  = n;while (true) {slow = Next(slow);fast = Next(Next(fast));if (fast == 1) {return true;} else if (fast == slow) {return false;}}}public static int Next(int n){int sum = 0;while (n != 0){int digit = n % 10;sum += digit*digit;n /= 10;}return sum;}public static void main(String[] args) {System.out.println(isHappy(19));}
}

当测试用例为2这个数字的时候

4 16 37 58 89 145 42 20 4 16 37 58 89 145 42 20 4 16 37 58 

第一步初始化slow和fast两个指针为头结点 (就是2)

第一次更新值

第二次

第三次

第四次

第五次

第六次

第七次

第八次

此时slow== fast

发现为循环链表(这里没有存储之前的值算不上链表)

return false

舒服了

如果觉得有用请点赞收藏, 谢谢啦

这篇关于力扣-202. 快乐数解析-弗洛伊德循环查找算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---