编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。
示例:
输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/happy-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思想:
只要平方和是之前出现过的数,那么递归就会陷入死循环,该数也不是快乐数,只要将出现过的数放入集合,每循环一次判断该数是否出现过即可。
在这里笔者用的是另一个方法。
1(快乐数)
2->4(最后循环到4)
3->9(最后循环到4)
4->16->37->58->89->145->42->20->4(死循环,非快乐数)
5->25->29->85->89(最后循环到4)
6->36->45->41->17->50->25(最后循环到4)
7->49->97->130->10->1(快乐数)
8->64->52->29(最后循环到4)
9->81->65->61->37(最后循环到4)
10->1(快乐数)
11->2(最后循环到4)
12->5(最后循环到4)
13->10->1(快乐数)
14->17(最后循环到4)
到这里可以得到一个结论,非快乐数会循环到4,也就是说,只要循环到4就可以判定该数为非快乐数。
代码实现:
class Solution { public boolean isHappy(int n) { if(n==4)return false; int res = 0; while(n!=0){ res += Math.pow(n%10,2); n /=10; } if(res==1)return true; else return isHappy(res); } }