题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 True ;不是,则返回 False 。
示例:
1
2
3
4
5
6
7 输入:19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/happy-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
关键点在于自己写几个数字的推演,其实题目中已经提到有两种情况:无限循环和收敛到 1。如果手写几个非快乐数的推演就会发现推演会陷入一个固定的数字循环中,问题变成链表环的检测,或者某个数出现第二次,说明进入了循环,此数不快乐。
1 | class Solution { |
另外,快慢指针的算法用于检查链表环,慢指针和快指针从同一起点出发,快指针每次移动两个,慢指针每次移动一个,如果存在链表环,两个指针最终相等,如果不存在,快指针率先找到链表尾部。
1 | class Solution { |
getnext
函数的时间复杂度为$lgN$,10为底,而收敛情况总能在常数次数内收敛,循环情况总能在常数次数内开始循环,因此最终时间复杂度$O(lgN)$。