有效的完全平方数

概述：给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。进阶：不要 使用任何内置的库函数，如  sqrt 。

输入：num = 16
输出：true输入：num = 14
输出：false

方法一：判断整数

思路：直接对 num 取根号，若其值为整数，即返回。

# 判断整数
# 直接对num取根号，若其值为整数，即返回。
class Solution:def isPerfectSquare(self, num: int) -> bool:return num ** 0.5 % 1 == 0

方法二：取余

思路：假设该数是一个完全平方数，那么对其根号取余得到 0 时，即返回。

# 取余
# 假设该数是一个完全平方数，那么对其根号取余得到 0 时，即返回。
class Solution:def isPerfectSquare(self, num: int) -> bool:return num % (num ** 0.5) == 0

方法三：pow() 方法

思路：思路和上面基本一致，不同在于用 pow() 方法计算得到。

# pow() 方法
# 思路和上面基本一致，不同在于用 pow() 方法计算得到。
class Solution:def isPerfectSquare(self, num: int) -> bool:return float.is_integer(pow(num, 0.5))

方法四：暴力循环

思路：从 0 开始枚举，若其平方恰好等于 num 时，即返回。

# 暴力循环
# 从 0 开始枚举，若其平方恰好等于 num 时，即返回。
class Solution:def isPerfectSquare(self, num: int) -> bool:x = 0square = 0while square <= num:if square == num:return Truex += 1square = x * xreturn False

方法五：二分查找

思路：思路和上面基本一致，但是我们可以用二分查找来优化搜索范围。

# 二分查找
# 思路和上面基本一致，但是我们可以用二分查找来优化搜索范围。
class Solution:def isPerfectSquare(self, num: int) -> bool:left, right = 0, numwhile left <= right:mid = (left + right) // 2square = mid * midif square < num:left = mid + 1elif square > num:right = mid - 1else:return Truereturn False

方法六：牛顿迭代法

思路：借助泰勒级数向零点逼近，取得整数解即可。

# 牛顿迭代法
# 借助泰勒级数向零点逼近，取得整数解即可。
class Solution:def isPerfectSquare(self, num: int) -> bool:x_0 = numwhile True:x_1 = (x_0 + num / x_0) / 2if x_0 - x_1 < 1e-6:breakx_0 = x_1x_0 = int(x_0)return x_0 * x_0 == num

总结

牛顿法属实勾起了我学习计算方法时候的痛苦回忆