202. 快乐数

Posted on | In
Words count in article: 445 | Reading time ≈ 2

题目

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例1：

1
2
3
4
5
6
7
输入: 19
输出: true
解释: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例2：

1
2
输入：n = 2
输出：false

提示：

  • 1 <= n <= 2^31 - 1

解法

解法一：

网络搜索到得知非快乐数有个特点，计算过程中肯定会有4出现，那么就可以用这个特性来判断了。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isHappy(int n) {
		while (n != 1 && n != 4) {
            int temp = 0;
            while (n > 0) {
            	int nn = n % 10;
            	temp += nn * nn;
                n /= 10;
            }
            n = temp;
        }
        return n == 1;
    }
}

解法二：

还可以用Set来做判断，计算出来的数字是否已经出现过了，如果出现过了表示已经进入了一个“环路”，那么肯定是非快乐数了。
解法二参考：https://my.oschina.net/Tsybius2014/blog/524681

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.HashSet;

/**
 * @功能说明：LeetCode 202 - Happy Number
 * @开发人员：Tsybius2014
 * @开发时间：2015年11月1日
 */
public class Solution {
    
    /**
     * 快乐的数
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
        
        int temp = n;
        HashSet<Integer> hashSet = new HashSet<Integer>(); 
        hashSet.add(temp);
        while (true) {
            temp = getNext(temp);
            if (temp == 1) {
                return true;
            } else if (hashSet.contains(temp)) {
                return false;
            }
            hashSet.add(temp);
        }
    }
    
    /**
     * 获取下一个快乐的数
     * @param num
     * @return
     */
    private int getNext(int num) {
        int result = 0;
        while (num > 0) {
            result += (num % 10) * (num % 10);
            num = num / 10;
        }
        return result;
    }
}
0%