我在理解Happy Number Question from Leet code的一个解决方案的空间复杂性分析时遇到了一些困难,对于我对复杂性分析的疑问,我用粗体标记了它们,非常感谢您的建议
问题是:
链接:https://leetcode.com/problems/happy-number/
问题:
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.
示例:
输入:19
输出:真
说明:
1^2(1的平方)+9^2=82
8^2+2^2=68
6^2+8^2=100
1^2+0^2+0^2=1
代码如下:
class Solution(object):
def isHappy(self, n):
#getnext function will compute the sum of square of each digit of n
def getnext(n):
totalsum = 0
while n>0:
n,v = divmod(n,10)
totalsum+=v**2
return totalsum
#we declare seen as a set to track the number we already visited
seen = set()
#we stop checking if: either the number reaches one or the number was visited #already(ex.a cycle)
while n!=1 and (n not in seen):
seen.add(n)
n = getnext(n)
return n==1
注意:如果我需要解释代码的工作原理,请随时告诉我
解决方案说空间复杂度是logN,有人能给我一些建议说明为什么会这样吗?
目前没有回答
相关问题 更多 >
编程相关推荐