问题

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

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

示例 1：

输入：16，输出：True

示例 2：

输入：14，输出：False

---

思路及代码

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
# # 方法一：（二分法）从1~num，选取low = start，high = end。
#         if num == 1: return True
#         if num == 2: return False
#         low = 1; high = num/2
#         while(high - low > 1):
#             mid = (low + high) // 2
#             if mid ** 2 == num:
#                 return True
#             elif mid ** 2 > num:
#                 high = mid
#             elif mid ** 2 < num:
#                 low = mid
#         else:
#             return False

# # 方法二：（暴力法）
#         for i in range(100000):
#             if i ** 2 == num:
#                 return True
#         return False

# 方法三：（巧妙地运用经验公式）
# 1 + 3 + 5 + 7 + ... + n = n^2，（即每一个完全平方数都可以分解成前n个奇数之和）
        i = 1; sum = 0
        while(sum < num):
            sum += i
            i += 2
        return sum == num  # 返回一个关系表达式的值（True or False）      

因为sqrt(1) = 1，sqrt(2) = 2^(1/2)，比2大的数字的开平方一定比 num/2 要小，所以high选取到 num//2+1 即可。

---

知识点 

1. Error：local variable 'x' referenced before assignment

原因：变量作用域的问题。

（参考：常见的local variable 'x' referenced before assignment问题）

（参考：python UnboundLocalError: local variable 'xxx' referenced before assignment）

2. Error：unindent does not match any outer indentation level

原因：Python的对齐问题。

（参考：Python脚本运行出现语法错误：IndentationError: unindent does not match any outer indentation level）