标签： 龟兔赛跑

202.快乐数

目标

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

「快乐数」 定义为：

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

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

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

1 <= n <= 2^31 - 1

思路

难点是如何确定停止条件，我甚至想过记录循环次数如果超过某一个数就返回false。我意识到这可能是一个数学问题，就放弃了。

看了题解才明白，问题看似是开放的，但也是有规律的，关键是如何分析这个问题。

考虑最终可能出现的情况：

  • 最终会得到 1。
  • 最终会进入循环。
  • 值会越来越大，最后接近无穷大。

考虑不同位数数字的最大值，进行一次计算的结果：

位数 最大值 下一个值
1 9 81
2 99 162
3 999 243
4 9999 324
13 9999999999999 81*13=1053

相应位上小于最大值的数字，其下一个值也必定小于最大值的下一个值。

意识到存在循环是很重要的，然后我们可以使用哈希表记录出现过的元素，也可以使用弗洛伊德循环检测算法（Floyd's Cycle-Finding Algorithm）又称为龟兔赛跑算法（Tortoise and Hare Algorithm），注意不是图论中求最短路径的弗洛伊德算法。

// todo 自己实现一下

代码

/**
 * @date 2024-06-15 20:59
 */
public class IsHappy202 {

    /**
     * 快慢指针，也是用来检测链表中是否存在环
     * 快慢如果相遇就说明存在环，否则快的先遇到1
     */
    class Solution_v1 {
        public int getNext(int n) {
            int totalSum = 0;
            while (n > 0) {
                int d = n % 10;
                n = n / 10;
                totalSum += d * d;
            }
            return totalSum;
        }

        public boolean isHappy(int n) {
            int slowRunner = n;
            int fastRunner = getNext(n);
            while (fastRunner != 1 && slowRunner != fastRunner) {
                slowRunner = getNext(slowRunner);
                fastRunner = getNext(getNext(fastRunner));
            }
            return fastRunner == 1;
        }
    }

    /**
     * Set记录每次的数字，如果重复就返回false
     */
    class Solution {
        private int getNext(int n) {
            int totalSum = 0;
            while (n > 0) {
                int d = n % 10;
                n = n / 10;
                totalSum += d * d;
            }
            return totalSum;
        }

        public boolean isHappy(int n) {
            Set<Integer> seen = new HashSet<>();
            while (n != 1 && !seen.contains(n)) {
                seen.add(n);
                n = getNext(n);
            }
            return n == 1;
        }
    }

    /**
     * 实际上只会存在一个循环4→16→37→58→89→145→42→20→4
     */
    private static Set<Integer> cycleMembers =
        new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));

    public int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        while (n != 1 && !cycleMembers.contains(n)) {
            n = getNext(n);
        }
        return n == 1;
    }

}

性能

略