【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

相关内容

热门资讯

安卓导航怎么重做系统,系统重做... 你的安卓导航是不是突然卡壳了,或者你只是想给它来个焕然一新的大变身?别急,今天就来手把手教你如何给安...
安卓手写平板系统重装,轻松恢复... 你那安卓手写平板系统是不是突然间就闹起了别扭,各种卡顿、崩溃,让你头疼不已?别急,今天就来给你详细说...
小米刷安卓13系统教程,小米手... 亲爱的米粉们,你是否已经迫不及待想要升级你的小米手机到最新的安卓13系统呢?别急,今天我就要手把手教...
语音包在哪里安卓系统,语音包生... 你有没有想过,有时候一句话就能让气氛瞬间活跃起来?没错,就是那些有趣的语音包!它们就像魔法一样,能让...
htc g10安卓系统,性能与... 你知道吗?最近我在手机圈里发现了一个小秘密,那就是HTC G10这款手机。这款手机搭载的安卓系统,简...
那几款手机是安卓系统 说到手机,安卓系统可是占据了半壁江山呢!市面上那么多手机,哪几款才是安卓系统中的佼佼者呢?今天,就让...
三星安卓系统评测,体验升级 你有没有发现,手机市场里总是有那么几个品牌,它们就像明星一样,总是能吸引我们的目光?今天,咱们就来聊...
老电脑装安卓6.0系统,轻松安... 你那台老电脑是不是已经服役多年,性能越来越不给力了?别急,今天就来给你支个招——给老电脑装上安卓6....
流畅度最高的安卓系统,揭秘安卓... 你有没有想过,为什么你的手机用起来那么顺滑,而别人的手机却总是卡得要命?这背后,其实隐藏着一个秘密—...
安卓手机系统服务在哪有,安卓手... 你有没有遇到过这种情况:手机里装了各种各样的应用,但是有时候想找某个服务却怎么也找不到?别急,今天就...
安卓11系统有哪些版本 你有没有发现,你的安卓手机最近是不是有点儿不一样了?没错,那就是安卓11系统的魅力所在!自从安卓11...
rog3安卓系统更新,体验极致... 亲爱的玩家们,你是否已经迫不及待地想要了解最新的Rog3安卓系统更新了呢?那就跟我一起,深入探索这次...
安卓系统隐藏应用appstor... 亲爱的手机控们,你是否曾好奇过,安卓系统里那些神秘的隐藏应用?没错,就是那些你不经意间就能发现,却又...
安卓系统车机互联软件 你有没有发现,现在开车的时候,手机和车机之间的互动越来越频繁了呢?想象你正驾驶着爱车,一边享受着音乐...
荣耀play4安卓系统,智能生... 你有没有发现,最近手机圈里又掀起了一股热潮?没错,就是荣耀Play4这款新机!它不仅外观时尚,性能强...
安卓模拟苹果多开系统,打造跨平... 你有没有想过,在安卓手机上也能享受到苹果系统的多开功能呢?没错,这就是今天我要跟你分享的神奇话题——...
广汽埃安是安卓系统吗,搭载安卓... 你有没有想过,你的爱车广汽埃安,它的操作系统是不是安卓呢?这个问题,估计不少车友都在心里默默琢磨过。...
安卓系统是google的吗,谷... 你有没有想过,安卓系统是不是谷歌的亲生孩子呢?这个问题,就像是在问苹果是不是苹果树的宝宝一样,让人好...
安卓系统的设置程序下载,轻松掌... 你有没有发现,手机里的安卓系统设置程序真是五花八门,让人眼花缭乱?今天,就让我带你一起探索这个神秘的...
安卓系统的手机家园,打造个性化... 你有没有发现,现在手机的世界里,安卓系统的手机家园可是越来越热闹了呢!想象每天打开手机,就像走进了一...