题目描述

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

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

示例:

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

标签 哈希表 数学

https://leetcode-cn.com/problems/happy-number/

一、题目给出的计算方式

获取每个位置上的数字的平方和，然后重复这个过程

二、依据计算方式，得到结果范围

• 每个位置上的数字范围：0~9
• 于1位数，平方和范围：1~81
• 对于2位数，平方和范围：1~162
• 对于3位数，平方和范围：1~243
• 整数最大位数是10位数(最大的整数2147483647)，那么平方和范围：1~810

可以看出，平方和总会回归到3位数，并进入 1~243 这个数字范围内

三、思路1：依据“快乐集合”和“不快乐集合”来判断

1. 既然所有整数，最终都会落到 1~243这个范围
2. 那么这些数字，肯定有的可以得到1，有的得不到，所以这些数字就可以分成两个集合，快乐集合 和 不快乐集合
3. 所以，如果一个整数，计算结果落在其中的一个集合，那么这个整数就是“快乐”或者“不快乐”的

四、思路2：依据是否循环来判断

1. 既然平方和结果范围是有限的，即1~243，那么只要可以不断计算下去，就必然是循环的
2. 程序可以检测到这种循环，进而判断整数非快乐数

五、时间复杂度分析

• 既然所有整数的平方和都会落在 1~243 这个范围内，那么就说明这个循环判定结果一定是有循环次数上限的，所以它是一个常数复杂度，即O(1)

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    if(n == 1 || n == 7) {
        return true;
    }
    if (n < 10) {
        return false;
    }
    let sum = 0;
    while(n >= 1) {
        let num = n%10;
        n = Math.floor(n/10);
        sum += num*num;
    }
    return isHappy(sum);
};