202. 快乐数

easy

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

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

• 如果这个过程 结果为 1，那么这个数就是快乐数。

示例 1：

输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2：

输入：n = 2
输出：false

哈希表

没别哒，就是把每一次的计算结果存起来，因为不是从头循环

func isHappy(n int) bool {
	hash := make(map[int]bool)
	sum := n
	for !hash[sum] {
		hash[sum] = true
		sum = getSum(sum)
		if sum == 1 {
			return true
		}
	}
	return false
}

func getSum(n int) int {
	sum := 0
	for n > 0 {
		sum += (n % 10) * (n % 10)
		n /= 10
	}
	return sum
}

快慢指针

慢指针走一步，快指针走两步，一定会相遇（都为 1 也是相遇的）

func getSum(n int) int {
	sum := 0
	for n > 0 {
		sum += (n % 10) * (n % 10)
		n /= 10
	}
	return sum
}

// 非常妙的快慢指针
func isHappy(n int) bool {
	slowSum, fastSum := n, n
	for {
		slowSum = getSum(slowSum)
		fastSum = getSum(fastSum)
		fastSum = getSum(fastSum)
		if slowSum == fastSum {
			break
		}
	}
	return slowSum == 1
}