首页
登录 | 注册

leetcode69 X的平方根的几种解法

第一种自然就是调APi啦(手动滑稽)

public int mySqrt(int x) {
        return (int)Math.sqrt(x);
    }

时间是52 ms,还超过了1/5的人呢

 

第二种 二分法

就是在0--X之间一半地一半地砍,最后直到左右边界的中间的数 = X/mid,这样做是防止因为mid数字太大而导致溢出

看代码吧,跟排序类似

public int getSqrtByDevide(int x) {
        if (x<=1) {
            return x;
        }
        int low = 0;
        int high = x;
        int mid = 0;
        while(low<=high) {
            mid = low + (high - low)/2;
            if(mid == (x/mid))
                return mid;
            else if(mid < (x/mid))
                low = mid + 1;
            else
                high = high -1;
        }
        return high;
    }

这种比上种稍微快一点:45 ms

 

第三种 牛顿迭代法 

刚开始还没搞懂是怎么回事,后来看了网上的一些帖子才明白.

首先拿此题来说,假设最后的输出的结果x² = N,(N是函数参数终点x),这里可以看成一个函数,即f(x) = x² - N;

那么最终的目的就变成了求这个函数的零点了

leetcode69 X的平方根的几种解法

迭代过程就是从X0开始,看它的平方是不是等于N,是就返回,不是就在X0对应的在函数图像上的点上做切线

再求这个切线和x轴的交点,重复上面的步骤:

f(x) = x² - N
设点Xi,则经过点(Xi,f(Xi))处的切线方程为g(x) = f(Xi)+ f'(Xi)(x - Xi)
令g(x) = 0
得x = Xi - f(Xi)/f'(Xi)
又f(Xi) = Xi² - N
代入得最终迭代式子:
x = (Xi + N/Xi)/2;

然后代码:

public int getSqrtByNewton(int x) {
        if (x<=1) {
            return x;
        }
        double last = -1;//最后
        double ans = 1;//结果
        while(last!=ans) {
            last = ans;//将迭代前的ans存起来,如果和迭代后ans相等,代表非常逼近
            ans = (ans+x/ans)/2;
        }
        return (int)ans;
        
    }

这个还是很快的:27ms

 

第四种 "0x5f3759df"算法 

这个的原理我也没搞太清楚,好像有个专门的论文将这个算法的,很神奇,经常用于图形学游戏领域一些场景里面

那我就只贴个代码吧(凑个字数...)

public int mySqrt(int x) {
        long t = x;
    t = 0x5f3759df - (t >> 1);
    while (!(t*t <= x && (t+1)*(t+1) > x))
        t = (x/t + t)/2;
    return (int)t;
    }

这里有讲,挺麻烦的,我就知道打一波666吧...

http://www.sandaoge.com/info/new_id/30.html?author=1

 


相关文章

  • 一.背景: 项目中有一些特殊的需求,如个别渠道继承腾讯bugly,个别渠道集成易观统计,不同的渠道集成不同的推送策略(如Oppo渠道优先Opush推送),不同的渠道拥有不同的第三方登录集成等等.这些需求本身,往往都与外部集成进来的功能有关, ...
  • [翻译 EF Core in Action 2.2] 创建应用程序的数据库上下文
    Entity Framework Core in Action Entityframework Core in action是 Jon P smith 所著的关于Entityframework Core 书籍.原版地址. 是除了官方文档外另 ...
  • numpy C语言源代码调试(一)
    近期学习numpy,希望了解numpy内部实现机制,尝试调试numpy的源代码,特别是其中的C语言源码. 在numpy的官方网站上,有numpy的开发人员手册: https://docs.scipy.org/doc/numpy/dev/ 通 ...
  • python接口自动化(二十三)--unittest断言——上(详解)
    简介 在测试用例中,执行完测试用例后,最后一步是判断测试结果是 pass 还是 fail,自动化测试脚本里面一般把这种生成测试结果的方法称为断言(assert).用 unittest 组件测试用例的时候,断言的方法还是很多的,下面介绍几种常 ...
  • 人性的弱点读书笔记   这是我第二遍读<人性的弱点>这本世界励志圣经,里面讲的很多东西到现在仍然很有实用价值,如果只是单纯的把它当做一本成功学的书籍,是比较比较浅薄的理解.人生于世,复杂而美妙,我们队我们自己的研究,对人性的探讨 ...
  • Spring入门(二):自动化装配bean
    Spring从两个角度来实现自动化装配: 组件扫描(component scanning):Spring会自动发现应用上下文中需要创建的bean. 自动装配(autowiring):Spring会自动满足bean之间的依赖. 为了更形象的解 ...

2020 cecdns.com webmaster#cecdns.com
12 q. 0.077 s.
京ICP备10005923号