[LeetCode]202 Happy Number

Question

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Solution

这道题一开始会想，我要怎么才能证明它被无限循环呢？一个程序不可能证明自己一直在无限循环，因为这个证明的时间是无限的。

其实这道题目隐藏了一个数学要素，如果它无限循环了，必然表明每次通过这个平方和的计算中，有一个数出现了两次，这样就形成了一个loop，产生了无限循环

所以我们可以利用各个语言中的set这个不含重复元素的数据结构，检查是否会出现相同的数

Code

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        s = set()
        while n!=1:
            if n in s:
                return False
            s.add(n)
            n = self.calculate(n)
        return True

    def calculate(self, n):
        total = 0
        for i in str(n):
            total = total + int(i)**2
        return total

s = Solution()
print s.isHappy(19)

注意很多语言中都有set这个数据结构，Java中的new HashSet()，C++中的set <int>s，Python中的s = set()

用python想用一个函数map一个数各个数位非常简单，就用for i in str(n)，相比Java冗长的各个Collection的声明真是如开挂般爽，但是相比Javascript自带的map，还没有那么熟练

Question

Solution

Code

MORE

FEATURED TAGS

FRIENDS