LeetCode 之 JavaScript 解答第69题 —— X 的平方根（Squrt(x)）

Time：2019/4/17

Title: sqrt(x)

Difficulty: Easy

Author: 小鹿

题目：sqrt(x)

Implement int sqrt(int x) .

Compute and return the square root of x , where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

实现 int sqrt(int x) 函数。

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

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

Example 1:

Input: 4
Output: 2
复制代码

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.
复制代码

Solve:

▉ 问题分析

▉ 算法思路

1）此过程分为两种情况，负数和正整数，所以要对输入的 x 进行判断。
2）然后开始根据二分查找应该注意的「三个重点」写出无 bug 的代码。
3）对二分查找进行稍微的变体，因为我们可能查找的数并不是一个正整数，我们取整数部分就可以了，小数部分省略。

▉ 测试用例

1）输入 0
2）输入1
3）输入负数的 x
4）输入平方根为正整数的 x
5）输入平方根为小数的 x

▉ 代码实现

写二分查找代码需要注意的三点：

1）循环退出条件。

2）mid 的取值。

3）low 和 hight 的更新。

var mySqrt = function(x) {
     let low = 1;
     let high = x;
     // 如果 x 小于 0 输出 -1
     if(x < 0) return -1;
     // 循环终止条件
     while(low <= high){
        // mid 取值
        let mid = Math.floor(low + ((high - low)/2));
        // 判断平方是否小于等于
        if(Math.pow(mid,2) <= x){
            // 如果小于等于,如果下一值大于 x 则当前值为 x 平方根的最小整数值
            if(Math.pow(mid+1,2) > x || mid === high){
                return mid;
            }else{
                low = mid + 1;
            }
        }else{
            high = mid - 1;
        }
    }
    return 0;
};
复制代码

▉ 性能分析

▉ 小结

通过这个题我们可以总结一下：

1）如果问题涉及到查找，我们要想到使用二分查找来提高效率。

2）使用二分查找之前，判断问题是否满足二分查找的要求。

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！ Github：https://github.com/luxiangqiang/JS-LeetCode

欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。