Happy Number
从一个正整数 n 开始，反复将它替换为各位数字的平方和。例如，12 会变成 1² + 2² = 5。如果这个过程到达 1，n 就是快乐数；否则，它会永远在不包含 1 的数字之间循环。如果 n 是快乐数，返回 true；否则返回 false。
函数
- ninteger
- 要测试的正整数
- 返回值boolean
- 如果重复计算各位数字的平方和最终得到 1，则为 true；如果陷入无限循环，则为 false
约束条件
1 ≤ n ≤ 231-1
示例
- 输入
- n = 7
- 输出
- true
- 解释
- 7 变成 49，然后 4² + 9² = 97，然后是 130，再然后是 10，最后是 1。这个过程到达
1，所以 7 是快乐数。
- 输入
- n = 2
- 输出
- false
- 解释
- 2 会变成 4、16、37、58、89、145、42、20，然后又回到 4。从这里开始，这 8 个数字会不断重复，永远不会到达
1。
- 输入
- n = 100
- 输出
- true
- 解释
- 1² + 0² + 0² = 1，因此 100 经过一步后到达
1。
进阶
怎样快速统计从 1 到 10^6 的快乐数，并重复利用小于 1000 的数的答案，而不是每次都从头遍历？
提示
逐个打开提示，每个都会多透露一点。
手动尝试几个起始数字。7 经过 5 步到达 1，而 2 经过 8 步后回到 4。一个数字回到原值时，这说明了什么？
每个值都只取决于它前面的值，所以一旦某个数字重复，它后面的整个序列就会永远重复。问题就变成了：这个过程会先到达 1，还是先到达一个已经出现过的数字？
记录你访问过的数字集合，并在到达 1 或遇到重复数字时停止。为了保持内存占用恒定，从
n开始运行两个遍历指针，每轮一个走一步，另一个走两步；它们只能在循环内部相遇。
题解
这个遍历不会无限增长：10 位数最多会映射到 10 × 81 = 810，小于 1000 的数最多会映射到 243。因此，它会一直处于少于 1000 个值的范围内，并且必定会到达 1 或重复。这就是循环检测：记住你见过的值，或者让一个遍历者走得慢，另一个走得快。
记住你见过的每个数字
思路
把你访问过的每个数字都记录在哈希集合中，并在数字为 1 或重复出现时停止。下一个数字只取决于当前数字，所以一旦某个数字再次出现，之后的所有数字都会重复，而且 1 永远不会出现。对于 2，集合中会依次记录 2、4、16、37、58、89、145、42 和 20，下一个值 4 已经在集合中了。
第一步之后，每个值都小于 1000，因此可以用一个包含 1000 个条目的标记数组来代替集合。
算法
- 创建一个空的哈希集合
seen。 - 当
n不为 1 时，如果n在seen中，则返回false。 - 否则，将
n添加到seen，并将n替换为它的各位数字的平方和。 - 循环结束时，
n为 1：返回true。
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
seen = set()
while n != 1:
if n in seen:
return False # back at an earlier number: a loop without 1
seen.add(n)
n = digitSquareSum(n)
return True快慢指针（Floyd 环检测）
思路
每个数字都有一条箭头，指向它的各位数字的平方和，因此从 n 开始的路径要么到达 1，要么进入循环。Floyd 算法无需存储数据就能找到循环：slow 每轮走一步，fast 每轮走两步。
如果循环中没有 1，两个指针最终都会在循环中移动。每轮 fast 都会多走一步，因此它们会停在同一个数字上：以 2 为例，它们会在 7 轮后相遇于 42。如果路径到达 1，fast 会先到达并停在那里，因为 1 指向 1。以 7 为例，fast 依次经过 49、130、1，而 slow 还在 97。所需轮数是路径长度的一个小倍数，内存只需存储两个整数。
算法
- 编写一个辅助函数，返回一个数字各位数字的平方和。
- 将
slow = n，并将fast设为从n开始前进 1 步后的数字。 - 当
fast不等于 1 且slow不等于fast时，让slow前进一步，让fast前进两步。 - 返回
fast是否等于 1。
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
slow = n
fast = digitSquareSum(n)
# fast moves two steps for every step of slow; they meet only inside a loop.
while fast != 1 and slow != fast:
slow = digitSquareSum(slow)
fast = digitSquareSum(digitSquareSum(fast))
return fast == 1
易错点和边界情况
- 循环直到值为 1，没有其他退出条件。对于 2，这个循环永远不会结束。
- 让两个指针从同一个数字开始，并在第一次移动前检查
slow != fast。循环不会运行，7 会被判定为不快乐数。 - 返回
slow == 1。对于 7，fast会到达 1，循环停止时slow还在 97。 - 每当两个指针相遇，就声明
n是不快乐数。它们也会在 1 相遇，所以要检查相遇的位置。 - 对各位数字求和，或者对整个数平方。对于 12，下一个值是
1² + 2² = 5，不是 3，也不是 144。
常见问题3
快乐数的时间复杂度是多少？
O(log n)。第一步读取 n 的 O(log n) 位数字；之后的每个值都小于 1000，最多遍历 20 个数字就会到达 1 或出现重复。哈希集合会存储这些数字，而 Floyd 算法的空间复杂度为 O(1)。
为什么所有不快乐数最终都会变成 4？
检查 1000 以下的每个数字，可以发现有一个循环不包含 1：4、16、37、58、89、145、42、20，然后又回到 4。每个起始数字经过一步后都会降到 1000 以下，因此所有不快乐数都会落入这个循环。遇到 4 时停止是可行的，但你需要在面试中说明这一点。
快乐数与链表环有什么关系？
这两种方法都在询问：沿着每个项目的一条箭头前进，是否会回到已经访问过的项目。这里的箭头是各位数字平方和；在链表中，它是下一个指针。这就是快慢指针都能用常量空间解决这两类问题的原因。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isHappy(n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 7
预期输出
true