python 算法题——快乐数的多种解法_Python

题目描述：

编写一个算法来确定一个数字是否“快乐”。快乐的数字按照如下方式确定：从一个正整数开始，用其每位数的平方之和取代该数，并重复这个过程，直到最后数字要么收敛等于1且一直等于1，要么将无休止地循环下去且最终不会收敛等于1。能够最终收敛等于1的数就是快乐的数字。

例如：19是一个快乐数字，计算过程如下：

1^2+9^2=82
8^2+2^2=68
6^2+8^2=100
1^2+0^2+0^2=1
要求：当输入快乐的数字时，输出True，否则输出False。

思路：

1. 当输入的不是快乐数字时，会陷入一个无限循环，因此增加一个计数器 count 用来统计计算次数。设定当 count 达到2000次时，认为该数字不是快乐数字，跳出循环结束计算。
2. 因为不确定输入的数字会是几位数，因此不采用除法和取模的方法来获得数字的每一位数，而是利用 for 循环获取字符串类型数字的每一位来计算平方和。

代码：

				?

									#快乐的数字

									def getSumofSquares(num):

									    numStr=str(num) #将待计算的数字转换成字符串类型

									    sum=0

									    digitls=[int(x) for x in numStr] #从字符串中提取出每一位数字存入一个列表

									    #注：该步略显多余，因为python中字符串可以和列表一样切片取值或循环，见下方更新部分

									    #print(digitls)

									    for i in digitls:

									        sum += i**2

									    return sum

									def main():

									    n = input() #输入一个正整数

									    sumofSqrs = eval(n)

									    count = 0

									    while sumofSqrs != 1:

									        sumofSqrs = getSumofSquares(sumofSqrs)

									        count += 1

									        if count > 2000: #当计算次数超过2000次时，跳出循环结束计算

									            print("False")

									            break

									    else:

									        print("True")

									main()

改良版

根据网友在评论区提出的不快乐的数字最终会在 [4,16,37,58,89,145,42,20] 这些数字中无限循环，因此可以加入判断，当数字变为这些数字里的任意一个（比如4）时就结束循环，输出False，从而避免无限循环的产生。

修改后的代码：

				?

									#（新）快乐的数字

									def getSumofSquares(num):

									    numStr=str(num)

									    sum=0

									    for i in numStr:

									        sum += int(i)**2

									    return sum

									def main():

									    n = input() #n为一个正整数

									    sumofSqrs = eval(n)

									    while sumofSqrs != 1 and sumofSqrs != 4: #或 while sumofSqrs not in [1,4,16,37,58,89,145,42,20]

									        sumofSqrs = getSumofSquares(sumofSqrs)

									    else:

									        if sumofSqrs == 1:

									            print("True")

									        else:

									            print("False")

									main()

采用递归

				?

									def happy(n):

									        try:

									                if n==1:

									                        print('True')

									                else:

									                        new = str(n)

									                        sum = 0

									                        for c in new:

									                                sum += int(c)**2

									                        return happy(sum)

									        except Exception as e:

									                print('False')

									                # print(e)

									n = eval(input())

									happy(n)

数学方法

				?

									d = {}

									while True:

									    m = 0

									    while n > 0:

									        m += (n%10)**2

									        n //= 10

									    if m in d:

									        return False

									    if m == 1:

									        return True

									    d[m] = m

									    n = m

优化过的

				?

									class Solution(object):

									    def isHappy(self, n):

									        """

									        :type n: int

									        :rtype: bool

									        """

									        record = []

									        sq_sum = 0

									        se_n = n

									        while se_n != 1:

									            sq_sum = 0

									            while se_n > 0:

									                sq_sum += (se_n % 10) * (se_n % 10)

									                se_n = se_n / 10

									            if sq_sum in record:

									                return False

									            record.append(sq_sum)

									            se_n = sq_sum

									        return True