Nuggets team number online, help you Offer impromptu! Click for details

I. Title Description:

Implement the int SQRT (int x) function.

Calculates and returns the square root of x, where x is a non-negative integer.

Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted

Example 1: Input: 4 Output: 2 Example 2: Input: 8 Output: 2 Description: The square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the code

Ii. Analysis of Ideas:

  • Math.sqrt(x)
  • Round down: ~~ or math.floor ()

AC code

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
  return ~~Math.sqrt(x)
};

Copy the code

Four,

  • There’s more than one way, of course;
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
  return Math.floor(Math.sqrt(x))
};

Copy the code

Officials offer several methods:

  • Binary search
  • Newton iteration
var mySqrt = function (x) {
    let l = 0, r = x;
    let res = 0;
    while (l <= r) {
        let mid = Math.floor((l + r) / 2);
        if (mid * mid == x) { return mid; }
        else if (mid * mid < x) {
            res = l;
            l = mid + 1;
        }
        else if (mid * mid > x) { r = mid - 1; }
    }
    return res;
};



var mySqrt = function (x) {
    if(x<=0) return x;
    let res;
    for(let i = 1; i <= x; i++){
        if(i * i <= x && (i+1)*(i+1) > x){
            res = i;
            return
        }
    }
    return res;
}
Copy the code

For learning reference only

Refer to the topic

  • Force link (LeetCode)