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

sf_wangchong 發布于2019-08-23 17:00 / 2183人閱讀

摘要：測試用例輸入輸入輸入負數的輸入平方根為正整數的輸入平方根為小數的代碼實現寫二分查找代碼需要注意的三點循環退出條件。使用二分查找之前，判斷問題是否滿足二分查找的要求。

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算法題新手求解答一下

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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