快乐数

题目：202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 231 - 1

方法一：

注意无限循环这个词，这代表一个数按照上述操作总会遇到曾经执行过的数。所以有如下写法：

func isHappy(n int) bool {//	定义一个切片存储每次计算后得到的值arr := make([]int64, 0)// 定义一个map存储各个位数m := make(map[int]int64)wei := 0var sum int64 = 0for !isInArr(arr, sum) {if sum != 0 {arr = append(arr, sum)n = int(sum)sum = 0}for n != 0 {m[wei] = int64(n) % 10n /= 10wei++}wei = 0for k, v := range m {sum += v * vdelete(m, k)}if sum == 1 {return true}}return false
}func isInArr(arr []int64, sum int64) bool {for _, i2 := range arr {if i2 == sum {return true}}return false
}

但是我们使用一个isInArr()函数检查结果是否已经出现过，这明显是浪费时间的。可以改为：使用map集合，结果作为key值，如果曾经存过直接返回false，遇到1返回true。

方法二：

map集合寻找值：

func isHappy(n int) bool {// 定义一个结果集res := make(map[int64]struct{})// 定义一个map存储各个位数m := make(map[int]int64)wei := 0var sum int64 = 0ok := falsefor !ok {if sum != 0 {res[sum] = struct{}{}n = int(sum)sum = 0}for n != 0 {m[wei] = int64(n) % 10n /= 10wei++}wei = 0for k, v := range m {sum += v * vdelete(m, k)}if sum == 1 {return true}_, ok = res[sum]}return false
}

这就结束了吗？NoNoNo！

有兴趣的可以看看这个题解：https://leetcode.cn/problems/happy-number/solutions/21454/shi-yong-kuai-man-zhi-zhen-si-xiang-zhao-chu-xun-h

因为不管是不是快乐数，最后总会陷入一个循环，所以我们只需要找出循环就行了。

找循环的方法前几天刚做过，就是快慢指针。

方法三：

func isHappy(n int) bool {// 快慢指针，f走两步，s走一步，如果有循环总会相遇，如果是1，又总会循环f, s := n, nsn := ss = 0// Go中不存在do while，所以需要先单独执行一遍，将第一个f==s 跳过for sn != 0 {s += (sn % 10) * (sn % 10)sn /= 10}for i := 0; i < 2; i++ {fn := ff = 0for fn != 0 {f += (fn % 10) * (fn % 10)fn /= 10}}for f != s {// s 走一步sn = ss = 0for sn != 0 {s += (sn % 10) * (sn % 10)sn /= 10}// f走两步for i := 0; i < 2; i++ {fn := ff = 0for fn != 0 {f += (fn % 10) * (fn % 10)fn /= 10}}}if f == 1 {return true} else {return false}
}