实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
这道题如果使用内置的开平方根函数非常简单，但是如果不使用呢？
其实利用「二分法」也可以非常简单的做出这道题，但是还有没有更好的算法呢，没错就是「牛顿迭代」。
假设我们现在要求 5 的平方根，既：
我们把它转换一下：
其实按照高中的数学知识，问题九转换成这就求方程：
与 y = 0 的交点。
我们来画一下函数的图像：
方程推导完了，我们来写代码：
class Solution1:
"""
二分查找法
"""
def mySqrt(self, x: int) -> int:
if x <= 1:
return x
left, right = 0, x
while left <= right:
mid = (left + right) / 2.0
if int(mid**2) > x:
right = mid
elif int(mid**2) < x:
left = mid
else:
return int(mid)
class Solution:
"""
牛顿迭代法
"""
def mySqrt(self, x: int) -> int:
if x <= 1:
return x
ans = x / 2.0
while ans**2 - x >= 1:
ans = (ans + x / ans) / 2
return int(ans)
解题代码仓库地址：https://github.com/elfgzp/Leetcode
顺便庆祝一下 Leetcode 解题数量经过几个月的努力终于破 200 啦🎉，附上自己的链接：
https://leetcode-cn.com/u/elfgzp/
The Log: What every software engineer should know about real-time data’s unifying abstraction - 日志：每个软件工程师都应该知道的有关实时数据的统一概念
推荐一个强化版 Vim 编辑器 - SpaceVim
SpaceVim 是一个社区驱动的模块化的 Vim IDE，以模块的方式组织管理插件以及相关配置， 为不同的语言开发量身定制了相关的开发模块，该模块提供代码自动补全， 语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱即用的 Vim IDE。
本人刚开始对 Vim 太熟悉，但是使用了 SpaceVim 之后，跟着官方的一些指引和 Google 上的一些 Vim 的教程，慢慢对这个编辑器产生兴趣。
个人是使用 SpaceVim + neovim 的，读者们可以参考一下。
最近因为两位 B 站 UP 主让我找回对数学的兴趣，放一下视频链接:
「珂学原理」No.95「骚代码是怎样炼成的」解剖快速平方根倒数算法
第一个视频介绍了魔数 0x5f3759df ，这个在耗子叔的极客时间的专栏也有出现过，第二个视频是牛顿迭代，如果 Algorithm 中笔者写的牛顿迭代没有看懂，可以看这个视频，「珂学原理」系列视频也非常有意思，推荐观看。
傅立叶变换如何理解？美颜和变声都是什么原理？李永乐老师告诉你
这个视频介绍了傅立叶变换，估计是我个人最喜欢的数学知识了，李永乐老师的其他视频也非常有意思，推荐观看。