202. 快乐数


202. 快乐数

难度简单 541
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:

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

如果 n 是快乐数就返回 true ;不是,则返回 false

示例 1:
输入:19
输出:true
解释:
1 + 9 = 82
8 + 2 = 68
6 + 8 = 100
1 + 0 + 0 = 1。

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)) &#123;
            seen.add(n);
            n = getNext(n);
        &#125;
        return n == 1;
    &#125;

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/
&#125;

用哈希集合检测循环

我们可以先举几个例子。我们从 7 开始。则下一个数字是 49(因为 77 =49),然后下一个数字是 97(因为 44+9*9=97)。我们可以不断重复该的过程,直到我们得到 1。因为我们得到了 7 是一个快乐数,函数应该返回 true。

再举一个例子,让我们从 116 开始。通过反复通过平方和计算下一个数字,我们最终得到 58,再继续计算之后,我们又回到 58。由于我们回到了一个已经计算过的数字,可以知道有一个循环,因此不可能达到 1。所以对于 116,函数应该返回 false。

根据我们的探索,我们猜测会有以下三种可能。

最终会得到 1 最终会进入循环。
值会越来越大,最后接近无穷大。
第三个情况比较难以检测和处理。我们怎么知道它会继续变大,而不是最终得到
1 呢?我们可以仔细想一想,每一位数的最大数字的下一位数是多少。

Digits Largest                 Next
1         9                         81
2         99                         162
3         999                         243
4         9999                  324
13         9999999999999 1053
对于

3 位数的数字,它不可能大于 243。这意味着它要么被困在 243 以下的循环内,要么跌到 1。
4 位或 4 位以上的数字在每一步都会丢失一位,直到降到 3 位为止。所以我们知道,最坏的情况下,算法可能会在 243 以下的所有数字上循环,然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去,所以我们排除第三种选择。

即使在代码中你不需要处理第三种情况,你仍然需要理解为什么它永远不会发生,这样你就可以证明为什么你不处理它。

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
剑指 Offer 28. 对称的二叉树 剑指 Offer 28. 对称的二叉树
剑指 Offer 28. 对称的二叉树难度简单 134请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。例如,二叉树  [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ /
2021-03-01 future
下一篇 
剑指 Offer 62. 圆圈中最后剩下的数字 剑指 Offer 62. 圆圈中最后剩下的数字
剑指 Offer 62. 圆圈中最后剩下的数字难度简单 3000,1,···,n-1 这 n 个数字排成一个圆圈,从数字 0 开始,每次从这个圆圈里删除第 m 个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。例如,0
  目录