202.快乐数

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

一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 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);
    }
}
上一篇:PKU 1026


下一篇:B - Frogger POJ - 2253(进阶最短路,青蛙跳跳跳)