【题目】
编写算法以确定数字n是否为“ happy”。
happy number的定义：以任意正整数开始，用该数中每个数字的平方和代替该数，然后重复此过程，直到数字等于1。否则它就会在不包含1的循环中无限循环（数学证明我也不清楚）。其中，以1结尾的数字是快乐数字。
如果n是一个快乐数字，则返回True；否则返回False。
example：
input：19
output：true
explanation：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
【本人解法】
class Solution: def isHappy(self, n: int) -> bool: l = [] while True: s = 0 for d in str(n): s += int(d)*int(d) if s == 1: return True if s in l: return False else: n = s l.append(s)
Runtime: 40 ms, faster than 29.61% of Python3 online submissions for Happy Number.
Memory Usage: 13.9 MB, less than 27.05% of Python3 online submissions for Happy Number.
相同意思另一种写法
def isHappy(self, n): mem = set() while n != 1: n = sum([int(i) ** 2 for i in str(n)]) if n in mem: return False else: mem.add(n) else: return True
class Solution: def isHappy(self, n: int) -> bool: memo = set() while n not in memo: memo.add(n) n = sum(int(i)**2 for i in str(n)) return 1 in memo
Runtime: 24 ms, faster than 98.44% of Python3 online submissions for Happy Number.
Memory Usage: 13.9 MB, less than 33.89% of Python3 online submissions for Happy Number.
【解法二】
Floyd cycle detection algorithm。在Linked list cycle detection问题中也用过。即快慢指针
class Solution: def isHappy(self, n: int) -> bool: def digitSquareSum(n): Sum = 0 while n > 0: n, d = divmod(n, 10) Sum += d*d return Sum slow, fast = n,n while True: slow = digitSquareSum(slow) fast = digitSquareSum(fast) fast = digitSquareSum(fast) if slow == fast: if slow == 1: return 1 else: return 0
Runtime: 36 ms, faster than 55.09% of Python3 online submissions for Happy Number.
Memory Usage: 13.8 MB, less than 72.99% of Python3 online submissions for Happy Number.
【解法三】
思路：在数字1-9中，2-6都不是快乐数，并且非快乐数都会陷入一个循环。
class Solution: def isHappy(self, n: int) -> bool: while n> 6: n = sum([int(i)**2 for i in str(n)]) return n==1
Runtime: 60 ms, faster than 8.31% of Python3 online submissions for Happy Number.
Memory Usage: 14 MB, less than 20.99% of Python3 online submissions for Happy Number.
class Solution: def isHappy(self, n: int) -> bool: while n> 6: next = 0 while n > 0: n, d = divmod(n, 10) next += d*d n = next return n==1
Runtime: 32 ms, faster than 78.81% of Python3 online submissions for Happy Number.
Memory Usage: 14 MB, less than 21.91% of Python3 online submissions for Happy Number.