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

sf_wangchong 发布于2019-08-23 17:00 / 2120人阅读

摘要：测试用例输入输入输入负数的输入平方根为正整数的输入平方根为小数的代码实现写二分查找代码需要注意的三点循环退出条件。使用二分查找之前，判断问题是否满足二分查找的要求。

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）根据题目要求，求一个指定树的平方根，第一要想到的是开平方根是没有规律可循的，可能想到一个暴力破解法，从 1 开始遍历，直到满足 k^2 < x 且 (k+1)^2 > x 为止。

2) 你可能想到这种方法效率太低，需要从 1 开始，如果 x 很大，岂不是需要遍历很多？能不能规定一个范围，在这个范围中查找开平方根呢？你会想到，所有数的开平方根得到的值是永远小于等于自身的（0 是自身），所以 x 的开平方根的值的范围一定在 0 < k < x 之间。

3）要想在这个区间快速定位找到一个满足条件的 x ，最高效的方法莫过于二分查找，但是可能存在小数，这又涉及到二分查找的四个变体（二分查找的变形）过程。如果你之前没有连接过，没关系，请看我之前记载的一篇文章。

4）虽然我们已经确定了解题方法，但是这时候不要着急，想一想这个问题是否满足二分查找的四个适用条件？哪四个条件呢？你需要系统学习一下就 ok ！

▉ 算法思路

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;
};

▉ 性能分析

暴力破解：

时间复杂度：O（n）。你需要从 1 遍历所有可能的数据，所以时间复杂度为O（n）。

空间复杂度：O（1）。不需要额外的内存空间。

二分法：

时间复杂度：O（n）。每次都折半查找，所以查找一个元素时间复杂度为O（logn）。

空间复杂度：O（1）。不需要额外的内存空间。

▉ 小结

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

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

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

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

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

云服务器 GPU云服务器希望你的解答谢谢 javascript平方根 javascript算法题新手求解答一下

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103662.html

leetcode 二分查找 - easy

摘要：如果目标值不存在于数组中，返回它将会被按顺序插入的位置。也因为是排序的数组，所以可以考虑二分法。计算并返回的平方根，其中是非负整数。输入输出说明的平方根是由于返回类型是整数，小数部分将被舍去。是一个非负整数，并且在位有符号整型的范围内。有时候会抽时间看看题目，锻炼一下简单记录下二分查找吧，会持续更新的啊哈~~~仅供参考，路过看下就行，欢迎交流~ 第35题给定一个排序数组和一个目...

objc94 2019-07-30 17:44 评论0 收藏0
LeetCode 之 JavaScript 解答第239题 —— 滑动窗口最大值（Sliding W

摘要：你只可以看到在滑动窗口内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。算法思路暴力破解法用两个指针，分别指向窗口的起始位置和终止位置，然后遍历窗口中的数据，求出最大值向前移动两个指针，然后操作，直到遍历数据完成位置。 Time：2019/4/16Title: Sliding Window MaximumDifficulty: DifficultyAuthor: 小鹿题目...

spacewander 2019-08-23 16:59 评论0 收藏0
LeetCode69. Sqrt(x) -- 求一个数的开方

摘要：牛顿迭代法的原理很简单，其实是根据在附近的值和斜率，估计和轴的交点，因此牛顿迭代法的公式为其实就是求切线与轴的交点。代码利用牛顿法进行的更新，比直接从开始遍历所作的循环要少牛顿迭代法的基本原理，请参考牛顿迭代法求开平方描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...

ddongjian0000 2019-07-30 16:55 评论0 收藏0
LeetCode 之 JavaScript 解答第169题 —— 求众数 I（Majority El

摘要：小鹿题目算法思路摩尔投票算法题目的要求是让我们求数组中超过一半数据以上相同的元素且总是存在的。 Time：2019/4/4Title: Majority Element 1Difficulty: easyAuthor: 小鹿题目：Majority Element 1 Given an array of size n, find the majority element. The ...

hightopo 2019-08-23 16:45 评论0 收藏0