Nuggets team number online, help you Offer rimmon! Click to see details

Square root of x (Question number 69)

The title

Implement 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 eliminated.

Example 1:

Input: 4 Output: 2Copy the code

Example 2:

Input: 8 Output: 2 Description: the square root of 8 is 2.82842... Since the return type is an integer, the fractional part will be omitted.Copy the code

link

Leetcode-cn.com/problems/sq…

explain

Is mainly binary search, because of their understanding of binary search is not in place, write some ugly code, but surprisingly is the performance of the orthodox binary search even better, may be due to a step more judgment, reduce some of the operation process.

Another Newton search is directly GG, this problem really won’t ah.

Your own answer (Binary search)

var mySqrt = function(x) { var left = 0 right = x while (left <= right) { var mid = parseInt((left + right) / 2) if (mid  * mid === x) { return mid } else if (mid * mid < x && (mid + 1)*(mid + 1) >x) { return mid } else if (mid * mid < x) { left = mid + 1 } else { right = mid - 1 } } };Copy the code

The above solution is actually using the characteristics of the problem, more than the ordinary binary search a layer of judgment conditions.

Because you’re just rounding, so if mid squared is less than x, and mid plus 1 squared is greater than x, then you can just return mid, and you don’t need to do anything else.

A better way (binary search)

var mySqrt = function(x) { var left = 0 right = x res = null while (left <= right) { var mid = ~~((right - left) / 2) + left if (x / mid === mid) { return mid } else if ( x / mid > mid ) { left = mid + 1 res = mid } else { right = mid - 1 }  } return res };Copy the code

Normal binary search. Nothing to say. The reason is not mid*mid but x/mid, is afraid that some numbers are too large to exceed JS maximum safe number, resulting in the program GG, except will not have this problem.

This condition is less than I write a step, but much more than I write a res, here it is, I put the result into the condition directly, so you don’t have to wait for a while after to return to, as long as can meet the conditions, I personally feel that the two methods can be, but this method is more in line with the specification of binary search, the code is very accord with the standard template, I’m improving it a little bit.

A better way (Newtonian iteration)

Var mySqrt = function(x) {// let r = x while (r ** 2 > x) r = ((r + x/r) / 2); | 0 return r };Copy the code

This problem is super, really won’t ah, use a mathematical formula, iterative can get the final result.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ