202. 快乐数

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

方案一

暴力求解

但是解题中存在漏洞

class Solution {
    public boolean isHappy(int n) {
        int tempNum = 0;
        
		// 此处循环次数存在问题，不确定多少的时候返回false
        for (int i = 0; i < 100; i++) {
            for (;;) {
                tempNum += (n % 10) * (n % 10);
                n = n/10;
                if (n == 0)
                    break;
            }

            if (tempNum == 1)
               return true;
            n = tempNum;
            tempNum = 0;
        }
        return false;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了86.60% 的Java用户
内存消耗:38.1 MB,击败了99.21% 的Java用户

分析

时间复杂度：
O( 100 * 位数 )

空间复杂度：
O( 1 )

官方题解

https://leetcode.cn/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/

总结：
本题目可能出现的情况有以下三种：

1. 最终会得到 1。
2. 最终会进入循环。
3. 值会越来越大，最后接近无穷大。
   其中第三条在本情况下可以排除。

因此只需要考虑前两种情况。
对于最终数值得到 1 很容易做到，因此，我们需要尝试去找到循环。

题解中提到两种方案：
方案一：将经历过的数据填入到数组，判断新的数据是否在数组中；
方案二：利用链表的思想，采用快慢指针的方式去实现，具体代码入下所示。

class Solution {

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

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。