leetcode-69. Sqrt(x)

Yuqi 發布于2019-07-30 17:22 / 2233人閱讀

摘要：題目思路牛頓迭代法，導數方程，任何函數，求解某個均可以轉化為此后就可以用牛頓迭代法，不斷逼近實際待求值。牛頓迭代共識應用迭代思想，類似于動態規劃思想，，進行動態推斷處理

題目：

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)

GPU云服務器云服務器 Sqrt x -x x python

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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