快乐数(Happy Number)

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

「快乐数」定义为：

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

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

示例 1：

输入：19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

示例 2：

输入：n = 2
解释：
2² = 4
4² = 16
1² + 6² = 37
3² + 7² = 58
5² + 8² = 89
8² + 9² = 145
1² + 4² + 5² = 42
4² + 2² = 20
2² + 0² = 4 
循环了，永远不会到1
输出：false

提示：

  • $1\leqslant n\leqslant2^{31}-1$

C语言的版本:

int next_n(int n){
    int r = 0;
    int d;
    while (n!=0){
        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[1000];
    int size = 0;
    while (!contains(history, size, n)){
        history[size] = n;
        size++;
        n= next_n(n);
    }

    return n == 1; 
}

快慢指针的版本:

int next_n(int n){
    int r = 0;
    int d;
    while (n!=0){
        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(next_n(fast));
    }while(slow != fast)
    return fast == 1;
}