leetcode 69. Sqrt(x)（python）

Little knowledge , Great challenge ！ This article is participating in “ A programmer must have a little knowledge ” Creative activities .

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 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 code 

Note:

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

analysis

Give a number in the title x , Ask to find out the square result of it , If it is an integer, the result will be returned directly , If it is a decimal result, only the integer part is returned , The idea is simple （ It's careless , Submitted several times and burst ERROR 了 , It's really a shame ）：

• Direct traversal [0, x // 2 + 2] Every integer in the range i
• If i * i == x , Go straight back to i
• If i * i > x , Go straight back to i-1

Even more humiliating is , The solution finally timed out , Read the requirements in the title , x The magnitude of is really too big ...

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 code 

Running results

Memory Limit Exceeded
 Copy code 

analysis

Of course, you can directly use the binary search method to find .

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 code 

Running results

Runtime: 37 ms, faster than 37.53% of Python online submissions for Sqrt(x).
Memory Usage: 13.3 MB, less than 66.04% of Python online submissions for Sqrt(x).
 Copy code 

analysis

Of course, using built-in functions can also , But more opportunistic .

answer

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

Running results

Runtime: 25 ms, faster than 61.40% of Python online submissions for Sqrt(x).
Memory Usage: 13.3 MB, less than 66.04% of Python online submissions for Sqrt(x).
 Copy code 

Original link ：leetcode.com/problems/sq…

Your support is my greatest motivation