【算法】求快乐数——快不快乐都要记下来

今天记一道题昂。是力口的
链接:https://leetcode-cn.com/probl...

反正就是呢有些数它是快乐的,你也不知道为啥,来先举个栗子:

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

快乐数的定义是:

首先我们定义一个方法叫“拆解平方求和”:意思是将一个正整数的每一位数字单独取出并求其平方,最后将结果加总得出一个新数字。

那么快乐数就指的是:将当前的数字进行拆解平方求和,并对其再次进行拆解平方求和,无限循环这个过程,如果最终数字可以变为 1,那么这个数就是快乐数。如果进入无限死循环,那就不是快乐数啦~


解题思路:
大致思路就是定义2个全局map,用来缓存已经验证是快乐或不快乐的数,之后循环判断的过程中只要来对应map里取一下结果就好了。以下这种结题思路主要运用了缓存和对象的索引。

来直接上答案,详细思路在注视里自己看昂:

/**
 * @param {number} n
 * @return {boolean}
 */
var happyMap = {};//全局记录一下快乐过的数
var unHappyMap = {};//也记录一下不快乐的数
var bro = {};//预备一个循环中要记录的当前循环数及衍生数的集合
var _getSum = function(num){
    var arr = (num+'').split('');
    var _sum  = 0;
    for(let i =0;i<arr.length;i++){
        _sum += Math.pow(arr[i],2)
    }

    if(_sum === 1){ //如果是1,直接返回true
        bro[num] = 1; //并将1记录下来~
        return true;
    }else if(bro[_sum]){ //如果是和当前循环的衍生数中某一个数撞上了,那么就是个死循环了,立刻返回false
        return false;
    }else if(happyMap[_sum]){ //如果是被记录为快乐数,则直接返回true
        return true;
    }else if(unHappyMap[_sum]){ //如果记录中不快乐,就返回false
        return false;
    }else{ //如果是个新的数,那就将它暂存在循环衍生map中
        bro[num] = 1;
        return _getSum(_sum);
    }
}
var isHappy = function(n) {
    bro = {}; //每一次新的循环,清空一次循环衍生数map
    var _flag = _getSum(n); //执行一次求和函数
    if(_flag){
        //如果是快乐的,那么这次衍生出的所有数都是快乐的,记录下来!
        for(let i in bro){
            happyMap[i] = true;
        }
    }else{
        //同理,如果只要结果不快乐,那过程都记到不快乐吧
        for(let i in bro){
            unHappyMap[i] = true;
        }
    }
    return _flag;
};

微信截图_20200501002417.png
反正就是还有好多好多思路,反正就是这个算法的速度贼快,且占用内存贼少(打败了辣么多的人,不知道咋算的,反正是厉害昂,偷笑hhhhhh)
来,原答案在这里:
https://leetcode-cn.com/probl...

评论

暂无评论