202. 快乐数

easy

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

「快乐数」 定义为：

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

示例 1：

1
2
3
4
5
6
7
输入：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：

1
2
输入：n = 2
输出：false

哈希表

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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 也是相遇的）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
}