LeetCode 69 题

Stella981
• 阅读 362

1.题目要求

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

2.初次尝试

这道题很明显不是让我们调用 Math.sqrt() 方法来计算,而是自己实现一个求平方根的算法。第一反应想到的方法是暴力循环求解!从 1 开始依次往后求平方数,当平方数等于 x 时,返回 i ;当平方数大于 x 时,返回 i - 1。

 1 class Solution {
 2     public int mySqrt(int x) {
 3         for(int i = 0; i <= x; i++) {
 4             if(i * i >= x){
 5                 if(i * i == x)
 6                     return i;
 7                 else
 8                     return i - 1;
 9             }
10         }
11         return 0;
12     }
13 }

这种方案通过了测试,但是成绩惨不忍睹:

执行用时 : 105 ms, 在Sqrt(x)的Java提交中击败了5.53% 的用户
内存消耗 : 33.1 MB, 在Sqrt(x)的Java提交中击败了83.60% 的用户

好奇心驱使下,我用了 Math.sqrt() 方法又提交了一遍答案:

1 class Solution {
2     public int mySqrt(int x) {
3         return (int)Math.sqrt(x);
4     }
5 }

成绩有点无解:

执行用时 : 5 ms, 在Sqrt(x)的Java提交中击败了99.24% 的用户
内存消耗 : 33.2 MB, 在Sqrt(x)的Java提交中击败了80.86% 的用户

这样一道乍看之下有点“蠢”的题目,其实有很多可以深究的地方。Math.sqrt() 用的是什么算法?求平方数的算法还有哪些?

Google 了一下“求平方根”,看到了两个出镜率最高的名词,一个是我们耳熟能详的“二分法”,另一个则是我第一次听说的“牛顿迭代法“。难得五一假期有空,决定了解一下”牛顿迭代法“并自己写出基于此算法的解题答案。

3.牛顿迭代法

我是根据知乎上一个回答了解牛顿迭代法的,链接贴出来了,有兴趣的朋友可以移步去看一下。这里简单的通过他的文章说明一下思路。

如何通俗易懂地讲解牛顿迭代法求开方?数值分析?​www.zhihu.com

这种算法的一个重要的思想是:切线是曲线的线性逼近。基于这种思想,牛顿尝试用切线来研究曲线的问题,例如用切线的根近似的求出曲线的根。然后他观察到一个现象,当在曲线上取某一点作切线时,以该切线的根作垂线,在垂线和曲线的交点处再作切线,以此循环往复,切线的根逐渐会逼近曲线的根。如图所示(A点时第一个取的点)。

LeetCode 69 题

当然,其实这种迭代并不是一定能保证会向曲线的根逼近,具体原因可以移步上述链接。但是求二次方程的根是没有问题的。

4.牛顿迭代法求平方根

回归到题目,求 a 的平方根,实际上可以转换成求二次方程 x^2 - a = 0 的解的问题。然后可以作出该二次方程的曲线,通过迭代逼近曲线 y = 0 处 x 的值,该 x 即是需要求得的答案。提现到程序中如下:

 1 class Solution {
 2     public int mySqrt(int x) {
 3         if(x == 1)
 4             return 1;
 5         double _x = x >> 1;
 6         double _y = _x * _x - x;
 7         double a = (-_y + 2 * _x * _x) / 2 / _x;
 8         while(_y > 0.1 || _y < -0.1){
 9             _x = a;
10             _y = _x * _x - x;
11             a = (-_y + 2 * _x * _x) / 2 / _x;
12         }
13         return (int)_x;
14     }
15 }

这个程序很直观的反应了迭代的过程,"_x" 是二次方程的横坐标,"_y" 是方程的纵坐标,"a" 是切线与 x 轴的交点处的横坐标。选取的第一点为 x / 2 作为横坐标,当 _y 的值逼近 0 的时候,返回 _x。该方法的成绩很接近 Math.sqrt(),结果为:

执行用时 : 6 ms, 在Sqrt(x)的Java提交中击败了92.91% 的用户
内存消耗 : 33.7 MB, 在Sqrt(x)的Java提交中击败了75.11% 的用户

5.简化

这里其实可以注意到,该二次方程一定是关于 y 轴对称的,而且二次方程在迭代过程中,若初始点在根的右边,则迭代的点会一直出现在根的右边,且一直逼近根。我们要找的其实是比根小的最大的整数,可以把 a 换成 int 类型,在逼近过程中,当 a 第一次小于等于 x / a 时,返回 a。

对程序进行简化,去掉一些不必要的参数,优化最后判断足够逼近的方式,最后程序为:

 1 class Solution {
 2     public int mySqrt(int x) {
 3         if(x == 1 || x == 0)
 4             return x;
 5         int a = x >> 1;
 6         while(a > x / a){
 7             a = (a + x/a) / 2;
 8         }
 9         return a;
10     }
11 }
点赞
收藏
评论区
推荐文章
刚刚好 刚刚好
1个月前
css问题
1、 在IOS中图片不显示(给图片加了圆角或者img没有父级) <div<img src""/</div div {width: 20px; height: 20px; borderradius: 20px; overflow: h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录 问题 用navicat导入数据时,报错: 原因这是因为当前的MySQL不支持datetime为0的情况。 解决修改sql\mode: sql\mode:SQL Mode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。 全局s
晴空闲云 晴空闲云
1个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。 盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
1个月前
快速入门|使用MemFire Cloud构建React Native应用程序
> MemFire Cloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Wesley13 Wesley13
1年前
MySQL的ROUND函数
* ROUND(_X_) ROUND(_X_,_D_) 返回参数_X_, 其值接近于最近似的整数。在有两个参数的情况下,返回 _X_ ,其值保留到小数点后_D_位,而第_D_位的保留方式为四舍五入。若要接保留_X_值小数点左边的_D_ 位,可将 _D_ 设为负值。 mysql> **SELECT ROUND(-1.23);**         ->
Wesley13 Wesley13
1年前
MYSQL分割字符串列转行
#准备示例数据 create table tbl_name (ID int ,mSize varchar(100)); insert into tbl_name values (1,'tiny,small,big'); insert into tbl_name values (2,'small,medium'); in
Wesley13 Wesley13
1年前
PHP中的NOW()函数
是否有一个PHP函数以与MySQL函数`NOW()`相同的格式返回日期和时间? 我知道如何使用`date()`做到这一点,但是我问是否有一个仅用于此的函数。 例如,返回: 2009-12-01 00:00:00 * * * ### #1楼 使用此功能: function getDatetimeNow() {
Wesley13 Wesley13
1年前
C语言常用函数大全
一、数学函数 调用数学函数时,要求在源文件中包下以下命令行: #include <math.h> **函数原型说明** **功能** **返回值** **说明** int abs( int x) 求整数x的绝对值 计算结果 double fabs(double x) 求双精度实数x的绝对值 计算结果 double acos(doub
helloworld_34035044 helloworld_34035044
4个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。 uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid() 或 uuid(sep)参数说明:sep 布尔值,生成的uuid中是否包含分隔符'',缺省为
helloworld_28799839 helloworld_28799839
1个月前
常用知识整理
# Javascript ## 判断对象是否为空 ```js Object.keys(myObject).length === 0 ``` ## 经常使用的三元运算 > 我们经常遇到处理表格列状态字段如 `status` 的时候可以用到 ``` vue