【leetcode】二分法和牛顿迭代法=>69
admin
2024-02-15 13:21:36
0

语法细节

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时要判断是否为0return 0y = int(math.exp(0.5*math.log(x))) # 我大无语,这里不能写成不加括号的1/2,要写(1/2)或0.5return y+1 if (y+1)**2<=x else y # y起名为ans更好# 注意是math.exp(),而不是直接exp()

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

class Solution(object):def mySqrt(self, x):""":type x: int:rtype: int"""if x == 0:return 0C, x0, xi = float(x), float(x), float('inf')while abs(x0 - xi) > 1e-7:xi = x0x0 = 0.5 * (xi + C / xi)return int(x0)

写法二:while+True

class Solution(object):def mySqrt(self, x):""":type x: int:rtype: int"""if x==0:return 0C,x0 = float(x),float(x)while True:xi = 0.5*(x0+ C/x0)if abs(xi - x0) < 1e-7: breakx0 = xireturn int(x0)

写法三:递归

class Solution(object):C = -1def mySqrt(self, x):""":type x: int:rtype: int"""self.C = xif x==0:return 0return int(self.sqrt(x))def sqrt(self,x):xi = 0.5*(x + self.C/x)# 当相邻两次迭代得到的交点非常接近时,我们就可以断定,此时的结果已经足够我们得到答案了if abs(xi-x) < 1e-7:return xielse:x = xireturn self.sqrt(x)

法三:二分法

class Solution(object):def mySqrt(self, x):""":type x: int:rtype: int"""left = 0right = x # 这里取x而不是x-1ans = -1 # 这里取-1,不要取0while left <= right:mid = left + (right-left)/2if mid**2 > x:right = mid -1elif mid**2 <= x:ans = midleft = mid +1return ans

相关内容

热门资讯

安卓系统可以放机械硬盘,存储扩... 你有没有想过,你的安卓手机或者平板,竟然可以装个机械硬盘?是的,你没听错,就是那种通常只出现在电脑里...
安卓系统好视界打不开,原因排查... 最近是不是你也遇到了这样的烦恼?你的安卓手机上那个好视界APP突然打不开啦!别急,让我来帮你一步步排...
幺妹直播安卓系统,安卓系统下的... 你有没有听说最近幺妹直播在安卓系统上大放异彩?没错,就是那个让无数网友沉迷其中的直播平台。今天,就让...
操作键位设置手机安卓系统 你有没有发现,手机上的那些操作键位设置,简直就像是我们日常生活中的小秘密武器呢?没错,就是那个小小的...
安卓系统怎么安装钱咖,轻松开启... 你有没有想过,手机里多一个赚钱的小帮手是多么美妙的事情呢?今天,就让我来带你一起探索如何在安卓系统上...
安卓系统鼠标键盘映射,安卓系统... 你有没有想过,你的安卓手机竟然也能变成一台电脑?没错,就是那种可以连接鼠标键盘,操作起来像模像样的电...
一加安卓系统耗电严重,深度剖析... 最近是不是发现你的手机电量像坐过山车一样,一会儿满电,一会儿就“嗖”地一下掉到谷底?别急,这可不是你...
汽车导航只有安卓系统吗,安卓系... 你有没有想过,为什么你的手机导航软件总是那么聪明,能带你轻松找到目的地呢?没错,这就是汽车导航的魅力...
未来的游戏推荐安卓系统,安卓系... 你有没有想过,未来的游戏世界会是什么样子呢?想象当你拿起手机,一款全新的游戏就在你的指尖跃动,那感觉...
安卓系统编程源码下载,下载与概... 你有没有想过,安卓系统背后的那些神秘代码是如何一步步编织出我们手中手机的精彩世界的?今天,就让我带你...
安卓系统ins如何设置私人,因... 你有没有发现,在Instagram上,有时候分享一些私密的内容,只想要特定的朋友看到,那可怎么办呢?...
安卓系统自带信息app,功能解... 你知道吗?手机里那些看似普通的信息应用,其实藏着不少秘密呢!今天,就让我带你一起探索一下安卓系统自带...
安卓系统看文档软件,探索高效便... 你有没有发现,手机里的安卓系统越来越强大了,各种应用层出不穷,让人眼花缭乱。今天,我就要给你安利一款...
安卓12系统oppo隐藏功能,... 你知道吗?最近安卓12系统在手机圈里可是掀起了一阵热潮呢!而作为手机界的一股清流,OPPO也悄悄地在...
塞班系统比安卓卡,为何比安卓系... 你有没有发现,手机用久了,有时候就像老牛拉车一样慢吞吞的?这不,最近有个话题在朋友圈里炒得挺热的,就...
安卓外卖系统教程视频,从入门到... 你有没有想过,点外卖竟然也能变得如此简单有趣?没错,就是那个让你在饥肠辘辘时,只需动动手指就能享受美...
mtk是安卓系统吗 你有没有想过,你的手机里那个神秘的MTK,它到底是不是安卓系统的一部分呢?别急,今天就来给你揭秘这个...
安卓系统改语言设置方法,安卓系... 你有没有发现,手机里的安卓系统突然变得陌生了呢?是不是想换一种语言来感受一下不同的文化氛围?别急,今...
电脑怎么换安卓系统恢复 你有没有想过,你的电脑突然间变成了安卓系统?别慌,这可不是什么天方夜谭,有时候,电脑系统的小变动也能...
安卓苹果系统漫画对比,操作系统... 你知道吗?在科技的世界里,两大巨头——安卓和苹果,就像是一对欢喜冤家,总是时不时地来一场“系统大战”...