一、Leetcode50——pow

【注意点】

1、n的值可以为正，负，0

2、O(n)会TLE，使用递归时，一定要将中间步保存

3、有博文中提到，若n<0，可以令n=-n, x = 1/x，但需要对n取反后是否出界进行处理，以下代码可以避免这个问题

【Python3代码】

class Solution:
    def myPow(self,x,n):
        if n == 0:
            return 1
        elif n == 1:
            return x;
        elif n == -1:
            return 1/x;
        else:
            temp = self.myPow(x,n//2)
            return temp*temp*self.myPow(x,n-n//2-n//2) 

二、Leetcode69——sqrt

【思路】

牛顿迭代法f(x) = x^2-a 的根，a即为要开方的数，根为开方的结果，首先任意给定x0一个非0的初值，根据牛顿迭代法易得x0的迭代公式为：x0 = (x0^2+a)/(2×0)

【Python3代码】

class Solution:
    def mySqrt(self, x):
        if x == 0:
            return 0
        else:
            x0 = x
            x1 = (x0*x0+x)/2/x0
            while(abs(x0-x1) > 0.1):
                x0 = x1
                x1 = (x0*x0+x)/2/x0
            return int(x1)