LeetCode 202. 快乐数

xiaoXingcode-go / 2023-05-07 / 原文

题目链接：LeetCode 202. 快乐数

题意：

本题是让我们判断一个数是否是快乐数，题干中给出了快乐数的条件。

解题思路：

方法一：

在题干中指出，如果一个数不是快乐数的话，那么它的各个位上的数字的平方和会无限循环，始终变不到1，

也就是说求和的过程中，sum会重复出现，因此我们抓住这一关键特征，判断在求和的过程中，sum是否循环出现，如果循环出现，就判定该数字不是快乐数，直接return false

否则直到求和sum为1为止。

完整代码如下：

func isHappy(n int) bool {

    // 题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
    // 所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
   
    set:=make(map[int]bool) 
    for n != 1 && !set[n] {
        n, set[n] = getsum(n), true
    }
    return n == 1
}
func getsum(n int)int{
    sum := 0
    for n > 0{
        tmp := n%10  //求一个数上 各个位上的数字
        sum += tmp*tmp
        n/=10
    }
    return sum
}

方法二：

1、 为什么一定是会循环出现：
有题干给出的数据范围可知，1 <= n <= 2^31 - 1，也就是说n最多有10位即最大的数为9999999999（10个9），那么此时求和sum = 9910=810，

因此，求和sum和取值范围就是[0,810]，一共811个数，因此，当我们求和操作的次数超过811次时，（例如812次）必然会有两个数字相等，

那么此时如果这个重复的数是 1 ，则是快乐数，否则不是快乐数。

2、当发生循环出现时，是不是相当于出现的环，也就是说一个数，经过多次的变换，最终出现了循环，这不就类似LeetCode 142. 环形链表 II这道题，

如下图所示：

此时我们就是要判断在链表的环中，数字是否是1，如果是1，则一定是快乐数，否则不是。

完整代码如下：

func isHappy(n int) bool {

    fast:=getsum(n)  //初始时，快指针比慢指针多走一步
    slow:=n //慢指针初始时，还没进行操作

    for fast != slow {
        fast = getsum(getsum(fast))   //快指针每次走两步
        slow = getsum(slow)  //慢指针每次走一步
    }
    return fast == 1


}
func getsum(n int)int{   //求和函数
    sum:=0
    for n > 0 {
        sum += (n%10) * (n%10)
        n/=10
    }
    return sum 
}