【Python3】【力扣题】367. 有效的完全平方数

本文介绍: 【Python3】【力扣题】367. 有效的完全平方数（python 函数，依次判断，二分查找，牛顿迭代法）

【力扣题】题目 描述：

【Pyt h on3】代码：

1、解题思路：Pyt h on 函数。num的平方根或者 num的0.5次幂。

知识点：float.is_integer(…)：判断浮点数的值是否等于整数。也可以：浮点数.is_integer()。

pow(a,b)：即 $a^{b}$ ，内置函数。

math.pow(a,b)：即 $a^{b}$ 。

opera tor.pow(a,b)：即 $a^{b}$ 。

math.sqrt(num)：num的平方根，即 $sqrt{num}$ 。

补充：pow(a,b)：指数为浮点数，则结果为浮点数；指数为整数，则结果为整数。且结果是近似值。

math.pow(a,b)：结果都是浮点数，且结果是精确浮点数。

operator.pow(a,b)：与内置运算符对应的高效率函数。结果同pow(a,b)一致。

class Solution:
    def isPerfectSquare(self, num: int) -&gt; bool:
        return float.is_integer(pow(num,0.5))
        # 或者
        import math
        return float.is_integer(math.pow(num,0.5))
        # 或者
        import operator
        return float.is_integer(operator.pow(num,0.5))
        # 或者
        import math
        return math.sqrt(num).is_integer()

2、解题思路：从1开始，依次判断其平方是否等于num。若其平方大于num，则不满足。

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        i = 1
        square = 1
        while square <= num:
            if square == num:
                return True
            i += 1
            square = i * i
        return False
        # 或者
        i = 1
        while i * i < num:
            i += 1
        return i * i == num

3、解题思路：二分查找。取1到num的中间值，若中间值的平方等于num，返回True。若中间值的平方小于num，则中间值开始的后半部分作为查找区间；若中间值的平方大于num，则从中间值的前半部分作为查找区间；再次取查找区间的中间值，比较其平方是否等于num。

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 0, num
        while left <= right:
            mid = left + (right-left) // 2
            square = mid * mid
            if square < num:
                left =  mid + 1
            elif square > num:
                right =  mid - 1
            elif square == num:
                return True
        return False

4、解题思路：牛顿迭代法。

牛顿迭代法：一种在实数域和复数域上近似求解方程的方法。其本质是借助泰勒级数，从初始值开始快速向函数零点逼近，即使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。广泛用于计算机编程。需注意：确定迭代值，迭代关系式，结束迭代的条件。

泰勒级数：无限项连加式（级数）来表示一个函数，这些相加的项由函数在某一点的导数求得。在近似计算中有重要作用。

导数：函数的局部性质。函数在某一点的导数描述了该函数在这一点附近的变化率。若函数的自变量和取值都是实数，函数在某一点的导数就是函数曲线上这一点的切线斜率。

斜率：一条直线（或曲线的切线）对于（横）坐标轴倾斜程度的量。若直线垂直于x轴，斜率不存在或称斜率无穷大；若直线平行于x轴，斜率为0；其余，直线y=k x+b，则斜率 $k=tanalpha =frac{y1-y2}{x1-x2}=frac{y2-y1}{x2-x1}$ 。

求导：微积分的基础。对函数求导，用 $f'left ( x right )$ 表示。可导的函数一定连续，连续的函数不一定可导。

详解：① 若num是完全平方数，则 $x^{2}=num$ ，因此 方程 $y=f(x)=x^{2}-num$ 。初始迭代值为 $x_{0}$ ，则 $y_{0}=x_{0}^{2}-num$ 。

② 对f(x)求导（导数公式： ${left (x^{n} right )}'=nx^{n-1}$ ， ${left ( C right )}'=0$ 其中C为常数）：f'(x)=2x。

③ 过当前迭代值( $x_{i}$ , $y_{i}$ )做一条斜率为该点导数的直线。即斜率 $k=2x_{i}=frac{y-y_{_{i}}}{x-x_{i}}$ ，该直线为 $y=2x_{i}x-x_{i}^{2}-num$ 。

④ 该直线与横轴的交点为 $(frac{x_{i}^{2}+num}{2x_{i}},0)$ ，横坐标为 $x_{i+1}=frac{1}{2}left ( x_{i}+frac{num}{x_{i}} right )$ 即下一个迭代值，根据方程计算出 $y_{i+1}=x_{i+1}^{2}-num$ 。

⑤ 重复③ ④ 依次迭代下去，若两次迭代值之间的差值小于极小的非负数 $epsilon$ (一般 $10^{-6}$ 或者 $10^{-7}$ )，则近似的获得结果。

注解：近似求解。初始迭代值为num，迭代关系式为(x0+num/x0)/2，终止迭代条件为x0-x1<1e-6。

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        x0 = num
        while True:
            x1 = (x0 + num / x0) / 2
            if x0 - x1 < 1e-6:
                break
            x0 = x1
        x0 = int(x0)
        return x0 * x0 == num