LeetCode Js-69. Sqrt(x)

    AllenLi
    LeetCode Js-Binary Tree

    Given a non-negative integer x, compute and return the square root of x.
    Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
    Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

    給予一個非負的整數 x，計算並回傳 x 的平方根。
由於返回的是整數的類別，故只回傳整數的結果。
注意：你不能使用任何指數函數，像是pow(x, 0.5) or x ** 0.5。

    Example 1:

    Input: x = 4
Output: 2

    Example 2:

    Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

    Solution:
    1. 宣告 r 等於 x。
    2. 當 (r * r > x)時，更新 r 為 (r + x / r) / 2 的整數
    3. 回傳 r。

    Code 1:

    var mySqrt = function(x) {
  let r = x

  while (r * r > x) {
    r = Math.floor((r + x / r) / 2)
  }

  return r
};

    牛頓迭代法

    FlowChart:
    Example 1

    Input: x = 4
r = x = 4

step.1 
while(4 * 4 > 4) => r = (4 + 4 / 4) / 2 => 5 / 2 = 2.5
r = Math.floor(2.5) = 2

step.2
while(2 * 2 > 4) => break

return r //2

    Example 2

    Input: x = 8
r = x = 8

step.1
while(8 * 8 > 8) => r = (8 + 8 / 8) / 2 => 9 / 2 = 4.5
r = Math.floor(4.5) = 4

step.2
while(4 * 4 > 8) => r = (4 + 8 / 4) / 2 => 6 / 2 = 3
r = Math.floor(3) = 3

step.3
while(3 * 3 > 8) => r = (3 + 8 / 3) / 2 => 5.67 / 2 = 2.83
r = Math.floor(2.83) = 2

step.4
while(2 * 2 > 8) => break

return r //2

時間複雜度：BigO(log n)
空間複雜度：BigO(n)

    Code 2:
    var mySqrt = function(x) {
    return Math.floor(Math.sqrt(x));
    };

    Related Posts