编写一个算法来判断一个数n
是不昰快乐数
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1如果可以变为1,那么这个数就是快乐数
如果 n 是快乐数就返回 True
;不是,则返回False
思路1:快慢指针(推荐,速度快)
- 既然是无限循环就容易想到环形链表。
- 快指针一次循环计算两次
- 慢指针一次循环计算一次
- 在无限循环过程中快慢指针一定会楿交。
- 如果相交点为1就说明是快乐数,反之不是
- 使用哈希表保存出现过的平方和。
- 如果再次出现且此数不为1就说明不是快乐数。反の就是快乐数