Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

describe

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.

Example 1:

Input: x = 4
Output: 2
Copy the code

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.Copy the code

Note:

0 <= x <= 2^31 - 1
Copy the code

parsing

If the number x is an integer, return the square root of the number x. If the number x is a decimal, return the square root of the number x.

  • Directly traverses every integer I in the range [0, x // 2 + 2]
  • If I * I == x, return I directly
  • If I * I > x, return I -1

To make matters worse, this solution finally ran out of time. After looking at the requirements in the problem, the magnitude of x is really too large…

answer

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        for i in range(0, x // 2 + 2):
            if i * i == x:
                return i
            if i * i > x:
                return i - 1
        	      
		
Copy the code

The results

Memory Limit Exceeded
Copy the code

parsing

Of course, binary search can be used directly to search.

answer

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l, r = 0, x
        while l <= r:
            mid = (l + r) // 2
            if mid ** 2 <= x < (mid + 1) ** 2:
                return mid
            elif x < mid ** 2:
                r = mid - 1
            else:
                l = mid + 1
Copy the code

The results

Given in the linked list (x). Submissions in the Python online list for Sqrt(X).Copy the code

parsing

Of course, you can use built-in functions, but it’s more opportunistic.

answer

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        return int(sqrt(x))
Copy the code

The results

Given in the linked list (x). Submissions in the Python online list for Sqrt(X).Copy the code

Original link: leetcode.com/problems/sq…

Your support is my biggest motivation