写点什么

ARTS-WEEK11

用户头像
一周思进
关注
发布于: 2020 年 08 月 23 日
ARTS-WEEK11

停了一周... 继续继续



Algorithm



本周学习二分查找



二分查找常用场景就是针对已排序的数组进行搜索,下面是代码实现:



def bsearch(list, num):
low = 0
high = len(list) - 1

while(low <= high): # 注意要包含等于,否则如果只有一个的情况下,还需要单独写if语句
mid = low + (high-low) // 2 # 这里注意不要写成 (low+high) // 2,否则可能溢出,也可以写成 low + (high-low) >> 2
if list[mid] == num:
return mid
elif list[mid] < num:
low = mid + 1
else:
high = mid - 1

return -1


# 递归实现
def bsearch_recursion(list, l, r, num):
if (l > r):
return -1

mid = l + (r-l) // 2
if (list[mid] == num):
return mid
elif list[mid] < num:
return bsearch_recursion(list, mid+1, r, num)
else:
return bsearch_recursion(list, l, mid-1, num)



LeetCode 对应练习:

https://leetcode-cn.com/problems/sqrtx/



然而自己并没有理解二分查找的精髓啊,实现的方式实际并没有套用二分查找的模板来写,也仍旧忘记考虑溢出的可能... 代码如下:



ABS_GAP = 1e-10 # print("%.10f"%(ABS_GAP)) 默认小数点后面保留6位

class Solution:
def mySqrt(self, x: int) -> int:
if (x == 1):
return 1

mid = x / 2
y = x
while (abs((mid*mid - x)) > ABS_GAP):
if (mid * mid > x):
y = mid
mid = mid / 2
else:
mid = (mid + y) / 2

return int(mid)



按二分查找模板改写后:



ABS_GAP = 1e-10 # print("%.10f"%(ABS_GAP)) 默认小数点后面保留6位

class Solution:
def mySqrt(self, x: int) -> int:
l = 0
r = x

if (0 == x or 1 == x):
return x

while (l <= r):
mid = l + (r-l) / 2
if (abs(mid - x/mid) <= ABS_GAP): # mid*mid -x 比较可能会越界
return int(mid)
elif (mid > x / mid):
r = mid
else:
l = mid



但是测试发现,mid 打印虽然显示是6.0000000000,int转换之后却是5了,将小数点保留位数扩大后,再重新打印mid,发现值是5.99999999999454303



了解了下 python 浮点数转整数的四种操作运算 int、round、ceil、floor,其中 int 是向0取整,round是四舍五入,math.floor是向下取整,math.ceil向上取整



增加了如下判断后,提交通过...



res = round(mid)
if (res * res) > x:
return int(mid)
else:
return round(mid)




当然看了官方题解,其实完全不用按浮点数来计算比较的,就是需要注意小于情况下需要保存当前的mid值,以便循环条件不满足时返回,代码如下:



class Solution:
def mySqrt(self, x: int) -> int:
l = 1
r = x
res = 0
y = 0

while (l <= r):
mid = l + (r-l) // 2
y = mid * mid

if (y == x):
return mid
elif (y > x):
r = mid - 1
else:
res = mid
l = mid + 1

return res



Review



《Automate the Boring Stuff with Python Practical Programming for Total Beginners》



这个目前看了80页,前面都是基础语法部分,没啥整理分享,不过可以说是第一次看英语技术书籍,发现还不是很难,继续坚持下去。



同时还在看《Professional CMake》来学习CMake,这个后面会整理下笔记分享分享。



Tip



vscode 像SI一样类似的标记高亮

可以安装插件 highlight-words



vscode 想SI一样类似的书签功能

可以安装插件 bookmarks



Share



这真是暴露了额外学习和输出的太少太少了...

后面这块得想办法补起来



发布于: 2020 年 08 月 23 日阅读数: 51
用户头像

一周思进

关注

每周学习总结,相信可以走的更远 2017.12.12 加入

嵌入式开发工程师 个人公众号:一周思进

评论

发布
暂无评论
ARTS-WEEK11