当前位置:   article > 正文

快乐数-用 HashSet 检测循环_hashset 循环

hashset 循环

方法一:用 HashSet 检测循环
我们可以先举几个例子。我们从 77 开始。则下一个数字是 4949(因为 7^2=497 
2
 =49),然后下一个数字是 9797(因为 4^2+9^2=974 
2
 +9 
2
 =97)。我们可以不断重复该的过程,直到我们得到 11。因为我们得到了 11,我们知道 77 是一个快乐数,函数应该返回 true。

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

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

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

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

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

算法:

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

给一个数字 nn,它的下一个数字是什么?
按照一系列的数字来判断我们是否进入了一个循环。
第 1 部分我们按照题目的要求做数位分离,求平方和。

第 2 部分可以使用 HashSet 完成。每次生成链中的下一个数字时,我们都会检查它是否已经在 HashSet 中。

如果它不在 HashSet 中,我们应该添加它。
如果它在 HashSet 中,这意味着我们处于一个循环中,因此应该返回 false。
我们使用 HashSet 而不是向量、列表或数组的原因是因为我们反复检查其中是否存在某数字。检查数字是否在哈希集中需要 O(1)O(1) 的时间,而对于其他数据结构,则需要 O(n)O(n) 的时间。选择正确的数据结构是解决这些问题的关键部分。

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/67297
推荐阅读
  

闽ICP备14008679号