每日一题 --- 快乐数[力扣][Go]

快乐数

题目：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 := 0
	var sum int64 = 0
	for !isInArr(arr, sum) {
		if sum != 0 {
			arr = append(arr, sum)
			n = int(sum)
			sum = 0
		}

		for n != 0 {
			m[wei] = int64(n) % 10
			n /= 10
			wei++
		}
		wei = 0

		for k, v := range m {
			sum += v * v
			delete(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 := 0
	var sum int64 = 0
	ok := false
	for !ok {
		if sum != 0 {
			res[sum] = struct{}{}
			n = int(sum)
			sum = 0
		}

		for n != 0 {
			m[wei] = int64(n) % 10
			n /= 10
			wei++
		}
		wei = 0

		for k, v := range m {
			sum += v * v
			delete(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, n
	sn := s
	s = 0
    // Go中不存在do while，所以需要先单独执行一遍，将第一个f==s 跳过
	for sn != 0 {
		s += (sn % 10) * (sn % 10)
		sn /= 10
	}
	for i := 0; i < 2; i++ {
		fn := f
		f = 0
		for fn != 0 {
			f += (fn % 10) * (fn % 10)
			fn /= 10
		}
	}
	for f != s {
		// s 走一步
		sn = s
		s = 0
		for sn != 0 {
			s += (sn % 10) * (sn % 10)
			sn /= 10
		}
		// f走两步

		for i := 0; i < 2; i++ {
			fn := f
			f = 0
			for fn != 0 {
				f += (fn % 10) * (fn % 10)
				fn /= 10
			}
		}
	}
	if f == 1 {
		return true
	} else {
		return false
	}
}