Poison

202. Happy Number

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();

        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = squareSum(n);
        }

        // 跳出时要不 n 等于 1, 要不遇到了环

        return n == 1;
    }

    private int squareSum(int n) {
        int sum = 0;
        while (n > 0) {
            int x = n % 10;
            sum += x * x;
            n /= 10;
        }
        return sum;
    }
}
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
class Solution {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = squareSum(n);

        while (fast != 1 && fast != slow) {
            slow = squareSum(slow);
            fast = squareSum(squareSum(fast));
        }

        // 跳出时要不 fast 等于 1, 要不遇到了环

        return fast == 1;
    }

    private int squareSum(int n) {
        int sum = 0;
        while (n > 0) {
            int x = n % 10;
            sum += x * x;
            n /= 10;
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    private static final Set<Integer> notHappyNumSet = new HashSet<>(Arrays.asList(2, 4, 16, 37, 58, 89, 145, 42, 20));

    public boolean isHappy(int n) {
        while (n != 1 && !notHappyNumSet.contains(n)) {
            n = squareSum(n);
        }

        // 跳出时要不 n 等于 1, 要不遇到了环

        return n == 1;
    }

    private int squareSum(int n) {
        int sum = 0;
        while (n > 0) {
            int x = n % 10;
            sum += x * x;
            n /= 10;
        }
        return sum;
    }
}
Reference

202. Happy Number