leetcode367-有效的完全平方数

原题

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

说明: 不要使用任何内置的库函数,如  sqrt

示例1:

输入: 16
输出: True

示例2:

输入: 14
输出: False

解法

思想

二分查找。由于平方后可能会超出int范围要注意long的使用。

代码

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

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode367-%e6%9c%89%e6%95%88%e7%9a%84%e5%ae%8c%e5%85%a8%e5%b9%b3%e6%96%b9%e6%95%b0/

发表评论

电子邮件地址不会被公开。