LeetCode: Sqrt

Title:

Implement int sqrt(int x).

Compute and return the square root of x.

思路：这个平方根肯定是在【1，x】之间，所以在这个区间使用二分查找。需要注意的是，代码中一直使用mid ，x/mid来比较，因为如果使用mid的平法，即使long long都会越界

class Solution {

public:

    int mySqrt(int x) {

        if(x<=)

        {

            return x;

        }

        int left = ;

        int right = x;

        while(left<=right)

        {

            int mid = (left + right)/;

            if(mid == x/mid)

            {

                return mid;

            }

            else if(mid < x/mid)

            {

                left = mid + ;

            }

            else

            {

                right = mid - ;

            }

        }

        return right;

    }

};

还可以使用牛顿迭代法

http://blog.csdn.net/doc_sgl/article/details/12404971

class Solution {

public:

    int mySqrt(int x) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if (x ==0)

            return 0;

        double pre;

        double cur = 1;

        do

        {

            pre = cur;

            cur = x / (2 * pre) + pre / 2.0;

        } while (abs(cur - pre) > 0.00001);

        return int(cur);

    }

};

巴特西

LeetCode: Sqrt

最新文章

热门文章