题目描述（简单难度）

给一个数字，将这个数字的各个位取平方然后相加，得到新的数字再重复这个过程。如果得到了 1 就返回 true，如果得不到 1 就返回 false 。

解法一

之前秋招的一道笔试题，当时想法也很简单。如果过程中得到了 1 直接返回 true 。 什么时候得不到 1 呢？产生了循环，也就是出现的数字在之前出现过，那么 1 一定不会得到了，此时返回 false。 在代码中，我们只需要用 HashSet 去记录已经得到的数字即可。 1. public boolean isHappy(int n) { 2. HashSet set = new HashSet<>(); 3. set.add(n); 4. while (true) { 5. int next = getNext(n); 6. if (next == 1) { 7. return true; 8. } 9. if (set.contains(next)) { 10. return false; 11. } else { 12. set.add(next); 13. n = next; 14. } 15. } 16. } 17. 18. //计算各个位的平方和 19. private int getNext(int n) { 20. int next = 0; 21. while (n > 0) { 22. int t = n % 10; 23. next += t * t; 24. n /= 10; 25. } 26. return next; 27. }

还有一个问题，代码中我们用了 while 循环，那么有没有可能永远不产生 1 并且不产生重复的数字，然后使得代码变成死循环呢？ 不需要担心，因为根据我们的算法，产生的数字一定是有限的。即使产生的数字不是有限的，因为我们用的是 int 来保存数字，int 所表示的数字个数是有限的。因此，如果产生的数字是 n 个，如果我们循环到第 n + 1 次，根据鸽巢原理，此时一定会产生一个重复数字了，从而跳出 while 循环。

解法二

参考 这里-space-and-no-magic-math-property-involved-))，优化了空间复杂度到 O(1)。 回想一下 141 题，判断一个链表是否有环。 而这道题，其实本质上就是判断链表是否有环，当出现重复的数字也就是产生了环。 所以我们可以用快慢指针的方法，或者叫 Floyd Cycle detection algorithm。 原理也很好理解，想象一下圆形跑道，两个人跑步，如果一个人跑的快，一个人跑的慢，那么不管两个人从哪个位置出发，跑的过程中两人一定会相遇。 所以这里我们用两个指针 fast 和 slow。fast 每次走两步，slow 每次走一步。 如果有重复的数字的话，fast 和 slow 就一定会相遇。 没有重复数字的话，当 fast 经过 1 的时候，就会停下来了。然后 slow 最终也会走向 1，所以也会相遇。 因此，代码的话，当 fast 和 slow 相遇的时候只需要判断当前是否是 1 即可。 1. public boolean isHappy(int n) { 2. int slow = n; 3. int fast = n; 4. do { 5. slow = getNext(slow); 6. fast = getNext(getNext(fast)); 7. } while (slow != fast); 8. return slow == 1; 9. } 10. 11. private int getNext(int n) { 12. int next = 0; 13. while (n > 0) { 14. int t = n % 10; 15. next += t * t; 16. n /= 10; 17. } 18. return next; 19. }

总

解法一很常规，解法二的话将模型归结到有环链表太厉害了，自愧不如。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情