第二类

与数学相关

• sqrt(X)
• pow(x, n)
• fastPower

sqrt(x)

这一题也是考察基本的，要注意的是，判断相等的条件是mid ** 2 <= target and (mid+1) ** 2 > target

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0 or x == 1:
            return x

        start, end = 0, x
        while start + 1 < end:
            mid = start + (end - start) / 2
            sqrt = mid ** 2
            sqrtPlus = (mid + 1) ** 2
            if sqrt <= x and sqrtPlus > x:
                return mid
            elif sqrt < x:
                start = mid
            else:
                end = mid

        if start ** 2 >= x:
            return start
        else:
            return end

pow(x,n)

这一题主要是递归类似二分法，每次递归求n/2的结果，再乘以自己，如果是奇数再乘以一个x 注意点

• n 是负数的情况
• n 是奇数的情况

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if x == 0:
            return 0
        if n == 0:
            return 1

        if n < 0:
            ret = self.myPow(x, -n)
            return 1 / ret

        ret = self.myPow(x, n / 2)
        ret *= ret

        if n % 2 != 0:
            ret *= x

        return ret