LeetCode202-快乐数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/happy-number/

中文链接：https://leetcode-cn.com/problems/happy-number/

题目详述

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

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

示例: 

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

题目详解

  • 按照要求进行操作，若是快乐数可以变为 1。
  • 若不是快乐数必然存在一个循环节。
  • 判断是否存在环即可。
  • 可以运用 HashSet。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00202 {

    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (n != 1) {
            if (!set.add(n)) {
                return false;
            }
            int sum = 0;
            while (n != 0) {
                int tail = n % 10;
                n /= 10;
                sum += tail * tail;
            }
            n = sum;
        }
        return true;
    }
}
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
public class LeetCode_00202 {

    public boolean isHappy(int n) {
        int fast = n;
        int slow = n;
        do {
            fast = getSqurareSum(getSqurareSum(fast));
            if (fast == 1) {
                return true;
            }
            slow = getSqurareSum(slow);
        } while (fast != slow);
        return false;
    }

    private int getSqurareSum(int n) {
        int sum = 0;
        while (n != 0) {
            int tail = n % 10;
            n /= 10;
            sum += tail * tail;
        }
        return sum;
    }
}
  • 根据数学定义，不是快乐数的数被定义为不快乐数。
  • 在计算过程中，不快乐数最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中。
  • 据此，如果我们发现计算过程中出现了数字 4 就说明是一个不快乐数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode_00202 {

    public boolean isHappy(int n) {
        while (n != 1 && n != 4) {
            int sum = 0;
            while (n != 0) {
                int tail = n % 10;
                n /= 10;
                sum += tail * tail;
            }
            n = sum;
        }
        return n == 1;
    }
}
  • 循环节 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 的长度为 8，最多可以操作 7 次。
  • 说明在验证是否是快乐数的过程中，若发现操作次数达到了 7 次，一定不是快乐数。
  • 快乐数在不超过 7 次操作过程中会变为 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00202 {

    public boolean isHappy(int n) {
        int cnt = 0;
        while (true) {
            int sum = 0;
            while (n != 0) {
                int tail = n % 10;
                n /= 10;
                sum += tail * tail;
            }
            n = sum;
            if (n == 1) {
                return true;
            }
            if (++cnt == 7) {
                return false;
            }
        }
    }
}