编写一个算法来判断一个数 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;
}