快乐数（环路检测）

本文主要是介绍快乐数（环路检测），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

写一个算法来判断一个数是不是”快乐数”。
一个数是不是快乐是这么定义的：对于一个正整数，每一次将该数替换为他每个位置上的数字的平方和，然后重复这个过程直到这个数变为1，或是无限循环但始终变不到1。如果可以变为1，那么这个数就是快乐数。
样例
19 就是一个快乐数。
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

快乐数

以十进位为例：
2 8 → 2²+8²=68 → 6²+8²=100 → 1²+0²+0²=1
3 2 → 3²+2²=13 → 1²+3²=10 → 1²+0²=1
3 7 → 3²+7²=58 → 5²+8²=89 → 8²+9²=145 → 1²+4²+5²=42 → 4²+2²=20 → 2²+0²=4 → 4²=16 → 1²+6²=37……
因此28和32是快乐数，而在37的计算过程中，37重覆出现，继续计算的结果只会是上述数字的循环，不会出现1，因此37不是快乐数。
不是快乐数的数称为不快乐数（unhappy number），所有不快乐数的数位平方和计算，最後都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中。

思路

类似于链表中检测是否有环路。显然要是快乐数，那么最后的环是在“1”的节点循环。要是不是快乐数那么就会在其他数中一直循环。因此巧妙的利用环路检测算法处理，可以高效的解决这个问题。

class Solution {
public:/*** @param n an integer* @return true if this is a happy number or false*/int calnumbers(int n){int res = 0;while(n){res = res + (n%10)*(n%10);n = n/10;}return res;} bool isHappy(int n) {// Write your code hereint low = n;int fast = n;//类似于链表中环形检测do{low = calnumbers(low);fast = calnumbers(fast);fast = calnumbers(fast);}while(low != fast);if(low == 1){return true;}else{return false;}}
};

这篇关于快乐数（环路检测）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---