leetcode with python:202. Happy Number

题目:

Write an algorithm to determine if a number n 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.
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.

Return true if n is a happy number, and false if not.

给定一个数字,决定它是不是happy number
happy number是指对一个数重複做各位数平方相加处理,最终结果会是1的数
ex:1^2+9^2=82
8^2+2^2=68
6^2+8^2=100
1^2+0^2+0^2=1
所以19是happy number

我觉得一个数不是happy number的原因
在于它在做各位数平方相加处理时会出现循环
因此我写了一个hash set来记录出现过的值

class Solution:    def isHappy(self, n: int) -> bool:        s=set()        while True:            if n==1:                return True            i=0            while n:                i=i+(n%10)**2                n=n//10            if i in s:                return False            s.add(i)            n=i

对该数不断做各位数平方相加,同时纪录出现过的值
一旦出现1就回传True
一旦出现set里的数就回传False
后面证明我的想法是对的(本来还抱持着一定会超时的想法去丢)
最后执行时间35ms(faster than 93.04%)

讨论区有人证出非happy number计算过程中一定会出现4

class Solution:    def isHappy(self, n: int) -> bool:        while True:            if n==1:                return True            i=0            while n:                i=i+(n%10)**2                n=n//10            if i==4:                return False            n=i

我是没特别去证明这件事啦
不过这样就不用用到hash set了
速度跟记忆体使用都会好一些
最后执行时间32ms(faster than 96.67%)

那我们下题见