V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  程序员

[Leetcode] 69. x 的平方根

  •  
  •   Acceml ·
    Acceml · 2018-09-15 23:37:30 +08:00 · 3788 次点击
    这是一个创建于 2021 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    实现 int sqrt(int x) 函数。

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

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

    示例 1:

    输入: 4
    输出: 2
    

    示例 2:

    输入: 8
    输出: 2
    说明: 8 的平方根是 2.82842..., 
    

    由于返回类型是整数,小数部分将被舍去。

    题解

    方法一:二分查找

    找到中间的数: mid = start + (end - start) / 2 而且: mid * mid <= x && (mid + 1) * (mid + 1) > x 但是这么写超出了 Integer 的范围了:

    class Solution {
        public int mySqrt(int x) {
            if (x == 0) return 0;
            int start = 1, end = x;
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (mid * mid <= x  && (mid + 1) * (mid + 1) > x)// Found the result
                    return mid;
                else if (mid > x / mid)// Keep checking the left part
                    end = mid;
                else
                    start = mid + 1;// Keep checking the right part
            }
            return start;
        }
    }
    

    所以改变一下: mid * mid <= x && (mid+1)(mid+1) > x 下面的 code 为 AC 版本:

    class Solution {
        public int mySqrt(int x) {
            if (x == 0) return 0;
            int start = 1, end = x;
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (mid <= x / mid && (mid + 1) > x / (mid + 1))// Found the result
                    return mid;
                else if (mid > x / mid)// Keep checking the left part
                    end = mid;
                else
                    start = mid + 1;// Keep checking the right part
            }
            return start;
        }
    }
    

    python 版本

    class Solution:
        def mySqrt(self, x):
            start, end = 0, x
            while start <= end:
                # 结果都计算为整数
                mid = start + (end - start) // 2
                if mid * mid <= x < (mid + 1) * (mid + 1):
                    return mid
                elif x < mid * mid:
                    end = mid
                else:
                    start = mid + 1
    

    牛顿迭代法

    基本思想:把非线性方程线性化,用线性方程的解逐步逼近原方程的解

    求某个数(比如 8)的平方根其实就是求解 f(x) = x^2 - 8 = 0 的解

    如上图

    点(x[k+1], 0)满足该方程 0 = f ( x[k]) + f'(x[k])(x[k+1] - x[k]) 得到牛顿迭代法的迭代公式:

    x[k+1] = x[k] - f(x[k]) / f'(x[k])

    回到求 8 的平方根

    x[k+1] = x[k] - (x[k] - 8) / (2 * x[k]) = (x[k] + 8 / x[k]) / 2

    就这样一直逼近到 x[k] * x[k] <= 8

    class Solution {
        public int mySqrt(int x) {
            if (x == 0) return 0;
            long i = x;
            while(i > x / i)
                i = (i + x / i) / 2;
            return (int)i;
        }
    }
    

    python 版本

    class Solution:
        def mySqrt(self, x):
            """
            :type x: int
            :rtype: int
            """
            if x == 0:
                return 0
            i = x
            while int(i) > int(x / i):
                i = (i + x / i) / 2
            return int(i)
    

    热门文章

    14 条回复    2018-09-25 00:41:21 +08:00
    Kilerd
        1
    Kilerd  
       2018-09-15 23:42:50 +08:00
    又来误人子弟了吗?
    easylee
        2
    easylee  
       2018-09-15 23:46:38 +08:00 via Android
    @Kilerd 此话怎讲?这里面有什么故事吗?
    zhuangzhuang1988
        3
    zhuangzhuang1988  
       2018-09-15 23:50:37 +08:00
    sicp 101
    broadliyn
        4
    broadliyn  
       2018-09-16 02:57:26 +08:00 via iPhone
    这种求近似解的
    高数里边极限等价替代、微分、泰勒公式套一下不就好啦。
    broadliyn
        5
    broadliyn  
       2018-09-16 03:07:22 +08:00 via iPhone
    也可以根据单调连续的函数零点左右的两个值乘积为负的特性再配合二分法可以逼出近似解。
    broadliyn
        6
    broadliyn  
       2018-09-16 03:16:45 +08:00 via iPhone
    除了上边的二分法,还有切线法,也就是 lz 的解法,没有 latex 排版表示看不懂 lz 在写什么。
    此外还有割线法,如果原函数的导数复杂的话,可以用割线来近似替代切线。

    上述出处是高数上册,微分中值定理与导数的应用里的泰勒公式、方程的近似解两章。
    RqPS6rhmP3Nyn3Tm
        7
    RqPS6rhmP3Nyn3Tm  
       2018-09-16 03:39:21 +08:00 via iPhone
    @Kilerd 解法没错,而且牛顿法很难想到,效率也很高
    puyo
        8
    puyo  
       2018-09-16 09:07:49 +08:00 via Android
    用雷神之锤法可不可以
    zingl
        9
    zingl  
       2018-09-16 12:01:19 +08:00
    aliipay
        10
    aliipay  
       2018-09-16 15:55:32 +08:00
    @puyo 我在自己机器上跑可以,是牛顿迭代法的 10 倍。 放到 leetcode 就执行出错
    CSM
        11
    CSM  
       2018-09-16 17:43:54 +08:00 via Android
    @puyo 我看到这个题第一个想到的就是雷神之锤😂
    Acceml
        12
    Acceml  
    OP
       2018-09-16 22:55:45 +08:00
    @Kilerd 你最正确,也最厉害,你尽管 diss,然而我并不 care 你...
    ayyll
        13
    ayyll  
       2018-09-16 23:14:43 +08:00 via Android
    为啥要发这里呀。。。还不如找个 oi 或者 acm 群水呢 。。这里的人都对解题报告这种东西不感冒吧
    20015jjw
        14
    20015jjw  
       2018-09-25 00:41:21 +08:00 via Android   ❤️ 1
    @easylee 他之前写了个很烂的答案.. 然后还强行 defend.. 喷点主要是名企们看到那个答案肯定没 offer..
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1010 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 22:03 · PVG 06:03 · LAX 15:03 · JFK 18:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.