哈希——202. 快乐数

偏执的太偏执、 2023-10-08 16:08 11阅读 0赞

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