LeetCode69. Sqrt(x) -- 求一个数的开方

ddongjian0000 发布于2019-07-30 16:55 / 1410人阅读

摘要：牛顿迭代法的原理很简单，其实是根据在附近的值和斜率，估计和轴的交点，因此牛顿迭代法的公式为其实就是求切线与轴的交点。代码利用牛顿法进行的更新，比直接从开始遍历所作的循环要少牛顿迭代法的基本原理，请参考牛顿迭代法求开平方

描述

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example：

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

分析

该题就是求一个数的开平方，此处忽略这种直接用int(x ** 0.5)的做法；

最简单的求解方式是从1进行遍历，直到找到一个数n，满足$n^2>x$，则此时$n-1$就是要找的值，但是该方法需要遍历$int(sqrt x)$次，当$x$的数值很大时，需要遍历的次数太多；

所以这里采用牛顿迭代法来进行开方，牛顿迭代法能开任意数的平方，并能找到一个逼近解，当然该题只需要找到对应的整数解就可以。牛顿迭代法的原理很简单，其实是根据$f(x)=x^2 - a$在$x_0$附近的值和斜率，估计$f(x)$和$x$轴的交点，因此牛顿迭代法的公式为：

$$x_{n+1}=x_n - frac{f(x_n)}{f^{"}(x_n)}$$

其实就是求切线与x轴的交点。

代码

class Solution:
    def mySqrt(self, x):
        """
        利用牛顿法进行x0的更新，比直接从1开始遍历所作的循环要少
        :type x: int
        :rtype: int
        """
        x0 = 1
        while True:
            x1 = x0 - (x0 ** 2 - x)/(2*x0)
            if int(x1) == int(x0):
                break
            else:
                x0 = x1
        return int(x0)

牛顿迭代法的基本原理，请参考：
牛顿迭代法求开平方

私有云 idc机房托管 linux求一列数据的和 Sqrt LeetCode x69x64 php

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41904.html

[Leetcode] Sqrt 开方

摘要：二分搜索复杂度时间因为整数长度有限空间思路我们知道必定存在这么两个整数和，所以我们要做的其实就是缩小这个的范围。代码牛顿迭代法复杂度时间空间思路更好的解法是用数学方法，牛顿法是非常经典的求解方程的方法。 Sqrt Implement int sqrt(int x). Compute and return the square root of x. 二分搜索复杂度时间 O(1) ...

BlackFlagBin 2019-08-14 12:25 评论0 收藏0
leetcode-69. Sqrt(x)

摘要：题目思路牛顿迭代法，导数方程，任何函数，求解某个均可以转化为此后就可以用牛顿迭代法，不断逼近实际待求值。牛顿迭代共识应用迭代思想，类似于动态规划思想，，进行动态推断处理题目： Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-neg...

Yuqi 2019-07-30 17:22 评论0 收藏0
[LeetCode] 69. Sqrt(x)

Problem Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated an...

SQC 2019-08-14 16:22 评论0 收藏0
LeetCode 之 JavaScript 解答第69题 —— X 的平方根（Squrt(x)）

摘要：测试用例输入输入输入负数的输入平方根为正整数的输入平方根为小数的代码实现写二分查找代码需要注意的三点循环退出条件。使用二分查找之前，判断问题是否满足二分查找的要求。 Time：2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿题目：sqrt(x) Implement int sqrt(int x). Compute and retu...

sf_wangchong 2019-08-23 17:00 评论0 收藏0