leetcode69-x的平方根

原题

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例1:

输入: 4
输出: 2

示例2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。

解法

思想

二分法

代码

class Solution {
    public int mySqrt(int x) {
        //为了防止end * end 超过int范围,这里统一使用使用long
        long longx = x;
        long start = 0;
        long end = x/2;
        long mid;
        while(start<=end){
            mid = (end+start)/2;
            if(mid*mid == longx) return (int)mid;
            if(mid*mid < longx) {
                start = mid + 1;
                if(start*start>longx) return (int)mid;
            }
            else if(mid*mid > longx) {
                end = mid - 1;
                if(end*end<longx) return (int)end;
            }
        }
        return (int)start;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode69-x%e7%9a%84%e5%b9%b3%e6%96%b9%e6%a0%b9/

发表评论

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