【leetcode】二分法和牛顿迭代法=＞69

语法细节

1、inf代表infinite,表示无限,亦即“无穷”.
inf分为 正无穷inf或+inf 和 负无穷-inf
Python中的表示方法是float(‘inf’)和float(‘-inf’)
求极值,也就是最大值,最小值的时候.用inf比取随机值作为初始值要优雅而准确得多
2、eN: 10的N次方
1e2 =1 * 10^2 =100
1.2e-5 =1.2 * 10^(-5) =0.000012
3、if not x:
如果x是0或者None或者 False, 空字符串"", 0, 空列表[], 空字典{}, 空元组()，那返回的就是真（true）
如果不是，就返回的是假（false）

在python中 None, False, 空字符串"", 0, 空列表[], 空字典{}, 空元组()都相当于False
None（N 必须大写）和 False 不同，它不表示 0，也不表示空字符串，而表示没有值，也就是空值，是NoneType类型的唯一值。

解法，重点关注牛顿迭代法

法一：袖珍计算器法

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0: # 注意把x装进log时要判断是否为0
            return 0
        y = int(math.exp(0.5*math.log(x))) # 我大无语，这里不能写成不加括号的1/2，要写(1/2)或0.5
        return y+1 if (y+1)**2<=x else y # y起名为ans更好
        # 注意是math.exp(),而不是直接exp()

1
2
3
4
5
6
7
8
9
10
11
12

法二：牛顿迭代法
注意当底数为0时无法逼近。所以此题必须判断x是否为0，如果为0，则直接return
写法一：while+条件

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
        C, x0, xi = float(x), float(x), float('inf')
        while abs(x0 - xi) > 1e-7:
            xi = x0
            x0 = 0.5 * (xi + C / xi)
        return int(x0)
1
2
3
4
5
6
7
8
9
10
11
12
13

写法二：while+True

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==0:
            return 0
        C,x0 = float(x),float(x)
        while True:
            xi = 0.5*(x0+ C/x0)
            if abs(xi - x0) < 1e-7: 
                break
            x0 = xi
        return int(x0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

写法三：递归

class Solution(object):
    C = -1
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        self.C = x
        if x==0:
            return 0
        return int(self.sqrt(x))
    
    def sqrt(self,x):
        xi = 0.5*(x + self.C/x)
        # 当相邻两次迭代得到的交点非常接近时，我们就可以断定，此时的结果已经足够我们得到答案了
        if abs(xi-x) < 1e-7:
            return xi
        else:
            x = xi
            return self.sqrt(x)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

法三：二分法

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left = 0
        right = x # 这里取x而不是x-1
        ans = -1 # 这里取-1，不要取0
        while left <= right:
            mid = left + (right-left)/2
            if mid**2 > x:
                right = mid -1
            elif mid**2 <= x:
                ans = mid
                left = mid +1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17