leetcode-69. Sqrt(x)

Yuqi 发布于2019-07-30 17:22 / 2239人阅读

摘要：题目思路牛顿迭代法，导数方程，任何函数，求解某个均可以转化为此后就可以用牛顿迭代法，不断逼近实际待求值。牛顿迭代共识应用迭代思想，类似于动态规划思想，，进行动态推断处理

题目：

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 1:
    Input: 4
    Output: 2
    Example 2:

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

思路：

牛顿迭代法， 导数方程 f"(x)*x"=y"，  任何函数f(x)=y，求解某个y=n,均可以转化为 f(x)-n=0,
        此后就可以用牛顿迭代法，不断逼近实际待求x值。
        牛顿迭代共识：f"(x_pre)x_pre+x_pre=x_cur
应用: 迭代思想，类似于 动态规划思想，pre==>cur，进行动态推断处理

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        r=x/2+1
        while r*r-x>1e-10:
            r=(r+x/r)/2
            # print(r*r-x)

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

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

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

摘要：牛顿迭代法的原理很简单，其实是根据在附近的值和斜率，估计和轴的交点，因此牛顿迭代法的公式为其实就是求切线与轴的交点。代码利用牛顿法进行的更新，比直接从开始遍历所作的循环要少牛顿迭代法的基本原理，请参考牛顿迭代法求开平方描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...

ddongjian0000 2019-07-30 16:55 评论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
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
【Leetcode】71. 简化路径

摘要：题目给定一个文档的完全路径，请进行路径简化。例如，边界情况你是否考虑了路径的情况在这种情况下，你需返回。此外，路径中也可能包含多个斜杠，如。文化和社会被恐惧所塑造，在将来这无疑也不会消失。题目给定一个文档 (Unix-style) 的完全路径，请进行路径简化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 边界情况:...

liuchengxu 2019-08-19 11:11 评论0 收藏0
【Leetcode】71. 简化路径

摘要：题目给定一个文档的完全路径，请进行路径简化。例如，边界情况你是否考虑了路径的情况在这种情况下，你需返回。此外，路径中也可能包含多个斜杠，如。文化和社会被恐惧所塑造，在将来这无疑也不会消失。题目给定一个文档 (Unix-style) 的完全路径，请进行路径简化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 边界情况:...

afishhhhh 2019-07-30 17:50 评论0 收藏0