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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：

首先需要将给出的数值进行拆分：
 

bool isHappy(int n) {int r = 0;n = 15646;while(n != 0){int d= n  % 10;n /= 10;  //r += d * d;printf("%d\n",d);}// printf("%d\n",r);return false;
} 

之后开始按照题目对其计算平方和，将代码封装起来

int next_n(int n)
{int r = 0;while(n != 0){int d= n % 10;n /= 10;  r += d * d;printf("%d\n",d);}return r;
}
bool isHappy(int n) 
{n = next_n(n);  printf("%d\n",n);return true;
} 

之后加上条件判断，当该数之前出现过时，则退出循环，未出现过则继续

int next_n(int n)
{int r = 0;while(n != 0){int d= n % 10;n /= 10;  r += d * d;}return r;
}
bool contains(int *history, int size , int n)
{for(int i = 0; i < size ; i++ ){if(history[i] ==n )return true;}return false;}
bool isHappy(int n) 
{int history[10000];int size = 0;while(!contains(history, size , n)){history[size] = n;size++;n = next_n(n);}  return n == 1;
} 

中间添加了一个条件判断，需要判断该数在之前有没有出现过。

实际上history最大只有9*9*10次，即810；

之后简化算法，利用龟兔赛跑，寻找重复数

int next_n(int n)
{int r = 0;while(n != 0){int d= n % 10;n /= 10;  r += d * d;}return r;
}bool isHappy(int n) 
{int slow = n;int fast = n;do{slow = next_n(slow);fast = next_n(fast);fast = next_n(fast);} while(slow != fast);return fast == 1;
}