每天一道leetcode69-x的平方根

前言

2018.10.31号打卡，今天你坚持了吗？

题目

leetcode 69 x的平方根

中文链接：

https://leetcode-cn.com/problems/sqrtx/

英文链接：

https://leetcode.com/problems/sqrtx/

分类：二分查找这一类

题目详情

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4输出: 2

示例 2:

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

题目详解

思路

1. 这个题目的话，使用二分查找，left是1，high是数字x；
2. 就是一个二分查找，不懂二分查找的看我的这篇文章，
3. 每次去计算mid*mid与数字x的大小，如果比x大，那么就令high去等于mid-1;比x小，就令low等于mid+1;等于x,那么直接返回mid;

代码

class Solution {
    public  int mySqrt(int x) {
        long low = 1;
        long high = x;
        while(low < high)
        {
            long mid = low + (high - low) / 2;
            if(mid * mid == x)
                return (int)mid;
            else if(mid * mid > x)
                high = mid - 1;
            else
                low = mid + 1;
        }
        if(low * low > x)
            return (int)(low - 1);
        return (int)low;
    }
}

1. 思路就是我上面说的思路，其中要注意的就是，由于mid*mid的大小很可能会超过int的最大取值，所以这里，把low,high,mid用long来表示；
2. 还有一点要注意的就是由于题目中要求返回的是int，所以这里应该最后进行类型转换；
3. 15-16行代码就是代表，low的平如果比x大，那么由于是向下取整，所以返回low-1;第17行代码，就表示low的平方是小于x的，那么直接返回low即可