Leetcode

69. Sqrt(x)

原思路 （Time Exceed）

遍历 0—> x, 直到遇到 sqrt(x)

1
2
3
4
5
6
7
8
9
class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        for i in range(x+1):
            if (i+1)**2 > x:
                return i

Improvement

Use Binary Search, 降低搜索时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:

    # dfs
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """

        def dfs (start,end):

            # int(float) method, 去小数点后面的数
            mid = int((start + end)/2)

            if mid **2 > x:
                return dfs(start,mid-1)
            else:
                if (mid+1) ** 2 > x:
                    return mid
                else:
                    return dfs(mid+1,end)

        return dfs(0,x)