0367. Valid Perfect Square (E)

佚名 4年前 (2020-07-05) 算法 617人围观抢沙发百度已收录

Valid Perfect Square (E)

题目

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example 1:

Input: num = 16
Output: true

Example 2:

Input: num = 14
Output: false

Constraints:

1 <= num <= 2^31 - 1

题意

判断一个整数是不是完全平方数，要求不能用内置方法。

思路

二分法，注意值越界问题。

代码实现

Java

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