Python练习笔记

Python练习笔记

最近在学习==Python==,所幸将练习记录一下:)

1.完美数

对于一个 正整数,如果它和除了它自身以外的所有 正因子 之和相等,我们称它为 「完美数」。

给定一个 整数 n, 如果是完美数,返回 true,否则返回 false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def checkPerfectNumber(self, num):
"""
:type num: int
:rtype: bool
"""
s=0
for i in range(1,num/2+1):
if num%i==0:
s+=i;
if s==num and s!=1:
return True
else:
return False

这是我的答案,但是并没有通过,超出时间限制了。。。

看了题解发现问题出现在

  1. 如果num 过大的话,每次从1开始循环,等待时间太久
  2. Math.sqrt,我们需要计算 num 除了它自身以外的所有正因子之和 sum,正因子必然是成对出现的,故而我们只需要遍历到 num 的平方根 sqrt 即可

36 为例,它的非自身外正因子有1、2、3、4、6、9、12、18,其中 1 和 6 单独计算,[2, 18]、[3, 12]、[4, 9]都是对应关系、
所以只需要遍历到 36 的平方根 6 就可以获取全部正因子,1单独计算的原因是要排除自身,6单独计算的原因是 6 * 6 = 36,两个值相同,故而只能计算一遍.题解

新的答案!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import math
class Solution(object):
def checkPerfectNumber(self, num):
"""
:type num: int
:rtype: bool
"""
s=1
for i in range(2,int(math.sqrt(num))+1):
if num%i==0:
s+=i
s+=num/i
if i*i==num:
s-=i
if s==num and s!=1:
return True
return False

时间复杂度 O(n**0.5),n 为 num 的大小

未完待续…

题目1来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/perfect-number