题目描述

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

实例：

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

题目链接

题解：

  常规方法当然是通过哈希表判重，即通过set(c++)记录每次计算得到的数来判断是否跳出循环。本文将介绍另一种方法，也就是利用Floyd Cycle思想来判断是否是1跳出循环。通俗来讲，就是快慢指针。
  题目给出了快乐数的定义，注意:是快乐数最终会变成1；若不是则可能掉入死循环。意味着我们要思考如何跳出循环。这时，利用快慢指针可破循环。为什么这么说？顾名思义，可以假设快慢指针在同一起点(也就是出入值n)出发，快指针一次计算两步，慢指针一次计算一步，那么，在某一时刻，无论它是不是快乐数，快慢指针都会相遇。也就意味着循环周期结束。这时，我们可以跳出循环，判断是否是1导致跳出循环。
  注：这里快慢指针分别走几步没有限制，掌握思想即可。当然，快两步慢一步效率相对高一些。

算法

  1. class Solution {
  2. public:
  3.     bool isHappy(int n) {
  4.         int slow = n, fast = n;
  5.         do{
  6.             slow = countNum(slow);
  7.             fast = countNum(fast);
  8.             fast = countNum(fast);
  9.         }while(slow != fast);
  10.         if(slow == 1){
  11.             return true;
  12.         }
  13.         else{
  14.             return false;
  15.         }
  16.     }
  18.     int countNum(int n ){
  19.         int sum = 0, temp = 0;
  20.         while(n > 0){
  21.             temp = n % 10;
  22.             sum += pow(temp , 2);
  23.             n = n / 10;
  24.         }
  25.         return sum;
  26.     }
  27. };

提示：

  当输入数为快乐数时，快慢指针最后一定会到达1，意味着快指针会先到达1，然后等着慢指针到达1再跳出循环。这使得我们会多出一部分运算，所以我们可以在快指针到达1时就跳出循环。

改进：

  1. class Solution {
  2. public:
  3.     bool isHappy(int n) {
  4.         int slow = n, fast = n;
  5.         do{
  6.             slow = countNum(slow);
  7.             fast = countNum(fast);
  8.             fast = countNum(fast);
  9.             if(fast == 1){
  10.                 return true;
  11.             }
  12.         }while(slow != fast);
  13.         if(slow == 1){
  14.             return true;
  15.         }
  16.         else{
  17.             return false;
  18.         }
  19.     }
  21.     int countNum(int n ){
  22.         int sum = 0, temp = 0;
  23.         while(n > 0){
  24.             temp = n % 10;
  25.             sum += pow(temp , 2);
  26.             n = n / 10;
  27.         }
  28.         return sum;
  29.     }
  30. };

若还有疑问可以去英文版leetcode的discuss区看大神们的解答！