给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例 1：

输入：16
输出：True
示例 2：

输入：14
输出：False

最开始想到的是使用sqrt()直接判断，什么？不能使用sqrt()?

不能使用任何内置的库函数，所以使用math.log的方案也挂掉了，老老实实去凑吧

1
2
3
4
5
6
7
8
9
10
def func(num):
    if(num<0):
        return False
    if(num<=2):
        return True
    for i in range(1,num//2):
        if(i*i==num):
            return True
        if(i*i>num):
            return False

虽然我觉得他肯定要卡你时间复杂度

果然后面他给我报错，MemoryError不过是发生在Line 7也就是for i in range(1,num//2):这一行就让我感觉有点意外

后来看到了公式，有点东西

4 = 1+3

9 = 1+3+5

16 = 1+3+5+7

以此类推

n^2 = 1+3+5+……+(2n-1)

所以我们就挨着挨着减下来就好了

1
2
3
4
5
6
7
8
def func(num):
    if(num<0):
        return False
    i = 1
    while(num>0):
        num-=i
        i+=2
    return num==0

只需要执行n次就可以了