367. 有效的完全平方数

1.题目

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

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

示例：

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

提示：

2.思路

首先我们要知道什么是完全平方数：完全平方指用一个整数乘以自己例如，，等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。

转换一下意思，也就是要找一个数x使得，也就是

暴力法：

public boolean isPerfectSquare(int num) {
        //解法一：暴力循环
        double i = 1;
        while(i * i < num){
           i++;
        }
        return i * i == num;
    }

对于这种单调函数，我们也可以使用二分法：

public boolean isPerfectSquare(int num) {
    if (num < 2) {
      return true;
    }
    long left = 2, right = num / 2, x, guessSquared;
    while (left <= right) {
      x = left + (right - left) / 2;
      guessSquared = x * x;
      if (guessSquared == num) {
        return true;
      }
      if (guessSquared > num) {
        right = x - 1;
      } else {
        left = x + 1;
      }
    }
    return false;
  }

根据公式：%3Dn%5E2#card=math&code=1%2B3%2B5%2B%5Ccdots%2B%282n-1%29%3Dn%5E2&id=Pkd1U)，可得：

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

牛顿迭代法（看不懂，救救我o(╥﹏╥)o）：

public boolean isPerfectSquare(int num) {
        if(1 == num) return true;
        int i = num / 2;
        while((double)i * i > num){
            i = (i + num / i) / 2;
        }
        return i * i == num;
}