Leetcode No.367有效的完全平方数牛顿迭代法

题目大意

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

输入：16
输出：True

示例2：

输入：14
输出：False

方法一：二分法

首先打表，存储int范围内的所有完全平方数，然后对表进行二分查找。

public boolean isPerfectSquare(int num) {
       int[] square = new int[((int)Math.sqrt(Integer.MAX_VALUE))+1];
        for(int i=0;i<square.length;i++)
            square[i] = i*i;
        int low = 0, high = square.length-1;
        while(low<high) {
            int mid = low + (high-low)/2;
            if(square[mid] == num) return true;
            else if(square[mid] < num) 
                low = mid + 1;
            else
                high = mid - 1;
        }
        return square[low] == num;
    }

运行时间4ms,击败14.13%。

方法三：暴力迭代超时

迭代的方法，依次尝试，这题会超时。

 public boolean isPerfectSquare(int num) {
         int i=0;
         while(i*i<num) 
            i++;
         return i*i==num;
     }

方法三：公式法

2^n = 1 + 3 + 5 +...+ 2*k-1

public boolean isPerfectSquare(int num) {
        int i=1;
        while(num>0) {
            num -= i;
            i+=2;
        }
        return num == 0;
    }

方法四：牛顿迭代法

image.png

因为此题求x^2 = n。构造函数f(x) = x^2 - n。
f'(x) = 2x.

 public boolean isPerfectSquare(int num) {
        int r = num;
        while((double)r*r > num) 
            r = (r + num/r)/2;
        return r*r ==num;
    }

运行时间0ms,击败100%。

Leetcode No.367有效的完全平方数 牛顿迭代法