LeetCode367Python—— 有效的完全平方数

有效的完全平方数

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

1.  
   输入：num = 16
2.  
   输出：true
3.  
    
4.  
   输入：num = 14
5.  
   输出：false

方法一：判断整数

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

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

方法二：取余

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

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

方法三：pow() 方法

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

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

方法四：暴力循环

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

1.  
   # 暴力循环
2.  
   # 从 0 开始枚举，若其平方恰好等于 num 时，即返回。
3.  
   class Solution:
4.  
   def isPerfectSquare(self, num: int) -> bool:
5.  
   x = 0
6.  
   square = 0
7.  
   while square <= num:
8.  
   if square == num:
9.  
   return True
10.  
    x = 1
11.  
    square = x * x
12.  
    return False

方法五：二分查找

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

1.  
   # 二分查找
2.  
   # 思路和上面基本一致，但是我们可以用二分查找来优化搜索范围。
3.  
   class Solution:
4.  
   def isPerfectSquare(self, num: int) -> bool:
5.  
   left, right = 0, num
6.  
   while left <= right:
7.  
   mid = (left right) // 2
8.  
   square = mid * mid
9.  
   if square < num:
10.  
    left = mid 1
11.  
    elif square > num:
12.  
    right = mid - 1
13.  
    else:
14.  
    return True
15.  
    return False

方法六：牛顿迭代法

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

1.  
   # 牛顿迭代法
2.  
   # 借助泰勒级数向零点逼近，取得整数解即可。
3.  
   class Solution:
4.  
   def isPerfectSquare(self, num: int) -> bool:
5.  
   x_0 = num
6.  
   while True:
7.  
   x_1 = (x_0 num / x_0) / 2
8.  
   if x_0 - x_1 < 1e-6:
9.  
   break
10.  
    x_0 = x_1
11.  
    x_0 = int(x_0)
12.  
    return x_0 * x_0 == num

总结

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

这篇好文章是转载于：学新通技术网