【算法】求快乐数——快不快乐都要记下来
文章目录
今天记一道题昂。是力口的
链接: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;
};

反正就是还有好多好多思路,反正就是这个算法的速度贼快,且占用内存贼少(打败了辣么多的人,不知道咋算的,反正是厉害昂,偷笑hhhhhh)
来,原答案在这里:
https://leetcode-cn.com/probl...
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论