367. Valid Perfect Square

题目：

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

 

Example 2:

Input: 14
Returns: False

链接：

https://leetcode.com/problems/valid-perfect-square/#/description

3/12/2017

遇到的问题：

1. num = 5的输入是总是time exceed，原因是mid值不改变，一直在特定值循环。解决方法：引入prevMid

2. 第10，11行的判断，出现的错误是808201，为什么mid值会一直变大呢？原因是如果用mid * mid == num判断的话，左边很有可能溢出。所以改为，商是mid，同时余数为0的判断。注意溢出值！！！

3. 其他解法：用质数的方法来判断，每当遇到能整除的值可以除去，看最后是否=1

public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num <= 2) return true;
        int low = 1, high = num;
        int mid = low + (high - low) / 2;
        int prevMid = 0;

        while (low <= high && mid != prevMid) {
            prevMid = mid;
            if (num / mid == mid && num % mid == 0) return true;
            else if (num / mid < mid) {
                high = mid;
                mid = low + (mid - low) / 2;
            } else {
                low = mid;
                mid = mid + (high - mid) / 2;
            }
        }
        return false;
    }
}

看别人算法之后精简，很值得思考的是，为什么low = mid + 1, high = mid -1？

个人猜测，当要改变low/high的时候，mid已经是不正确的值，如果mid + 1/mid - 1是正确的值的话，我们只会在另一个方向做更正，而一旦触及新的刚改变的low/high时，新的mid必定会返回true

public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num <= 2) return true;
        int low = 1, high = num;
        int mid;

        while (low <= high) {
            mid = low + (high - low) / 2;
            if (num / mid == mid && num % mid == 0) return true;
            else if (num / mid < mid) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}

还有牛顿法，需要记住

public boolean isPerfectSquare(int num) {
        long x = num;
        while (x * x > num) {
            x = (x + num / x) >> 1;
        }
        return x * x == num;
    }