快乐数

题目链接: https://leetcode.cn/problems/happy-number

解题思路：

1. 对于任何一个大于 $4$ 的数字，最终都会得到 $1$ 或 $4$，因此可以在循环中判断当前数字是否为 $4$，如果是，则直接返回 false

2. 当 n$ 不等于 1$或$4$$ 时，反复计算各个位上数字的平方和

func isHappy(n int) bool {
	for n != 1 { // 当n不等于1时，继续循环
		if n == 4 { // 如果n等于4，返回false
			return false
		}
		n = next(n) // 计算n的下一个数
	}

	return n == 1 // 如果n最终等于1，返回true
}

// next 返回 n 的各个位上数字的平方和
func next(n int) int {
	sum := 0
	for n > 0 { // 当n大于0时，继续循环
		digit := n % 10      // 取n的个位数字
		sum += digit * digit // 将个位数字的平方加到sum上
		n /= 10              // 将n的个位数字去掉
	}
	return sum // 返回各个位上数字的平方和
}

复杂度分析

• 时间复杂度： 时间复杂度是 $O(k)$，其中 $k$ 是最终得到 $1$ 或者 $4$ 的迭代次数。在最坏的情况下，迭代次数是一个循环链，其中每个数字都会被访问一次，因此迭代次数是有限的
• 空间复杂度： 空间复杂度是 $O(1)$，函数只使用了常数个变量来存储中间结果，没有使用额外的空间

map 解法：

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

	return true
}