哈希——202. 快乐数

1 题目描述

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

「快乐数」 定义为：

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

2 题目示例

示例 1：

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

示例 2： 输入：n = 2 输出：false

3 题目提示

1 <= n <= 231 - 1

4 思路

方法一:用哈希集合检测循环 我们可以先举几个例子。我们从7开始。则下一个数字是49(因为= 49)，然后下一个数字是97(因为42+92= 97）。我们可以不断重复该的过程，直到我们得到1。因为我们得到了1，我们知道7是一个快乐数，函数应该返回true 。 再举—个例子，让我们从116开始。通过反复通过平方和计算下一个数字，我们最终得到58，再继续计算之后，我们又回到58。由于我们回到了一个已经计算过的数字，可以知道有一个循环，因此不可能达到1。所以对于116，函数应该返回false 。 根据我们的探索，我们猜测会有以下三种可能。

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

第三个情况比较难以检测和处理。我们怎么知道它会继续变大，而不是最终得到1呢?我们可以仔细想—想，每—位数的最大数字的下一位数是多少。 对于3位数的数字，它不可能大于243。这意味着它要么被困在243以下的循环内，要么跌到1。4位或4位以上的数字在每一步都会丢失一位，直到降到3位为止。所以我们知道，最坏的情况下，算法可能会在243以下的所有数字上循环，然后回到它已经到过的一个循环或者回到1。但它不会无限期地进行下去，所以我们排除第三种选择。 即使在代码中你不需要处理第三种情况，你仍然需要理解为什么它永远不会发生，这样你就可以证明为什么你不处理它。

算法分为两部分，我们需要设计和编写代码。

1. 给一个数字n，它的下一个数字是什么?
2. 按照—系列的数字来判断我们是否进入了一个循环。

第1部分我们按照题目的要求做数位分离，求平方和。 第⒉部分可以使用哈希集合完成。每次生成链中的下一个数字时，我们都会检查它是否已经在哈希集合中。 如果它不在哈希集合中，我们应该添加它。 如果它在哈希集合中，这意味着我们处于一个循环中，因此应该返回false 。 我们使用哈希集合而不是向量、列表或数组的原因是因为我们反复检查其中是否存在某数字。检查数字是否在哈希集合中需要O(1)的时间，而对于其他数据结构，则需要O(n)的时间。选择正确的数据结构是解决这些问题的关键部分。

方法二:数学 前两种方法是你在面试中应该想到的。第三种方法不是你在面试中会写的，而是针对对数学好奇的人，因为它很有趣。 下一个值可能比自己大的最大数字是什么?根据我们之前的分析，我们知道它必须低于243。因此，我们知道任何循环都必须包含小于243的数字，用这么小的数字，编写一个能找到所有周期的强力程序并不困难。 如果这样做，您会发现只有一个循环:4→16→3758→89 >145—> 42→〉20 →> 4。所有其他数字都在进入这个循环的链上，或者在进入1的链上。 因此，我们可以硬编码一个包含这些数字的散列集，如果我们达到其中一个数字，那么我们就知道在循环中。

5 我的答案

方法一:用哈希集合检测循环

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;
    }
}

方法二:数学

class Solution {

    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;
    }
}