leetcode-69. Sqrt(x)

Yuqi 發(fā)布于2019-07-30 17:22 / 2231人閱讀

摘要：題目思路牛頓迭代法，導(dǎo)數(shù)方程，任何函數(shù)，求解某個均可以轉(zhuǎn)化為此后就可以用牛頓迭代法，不斷逼近實際待求值。牛頓迭代共識應(yīng)用迭代思想，類似于動態(tài)規(guī)劃思想，，進(jìn)行動態(tài)推斷處理

題目：

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.

思路：

牛頓迭代法， 導(dǎo)數(shù)方程 f"(x)*x"=y"，  任何函數(shù)f(x)=y，求解某個y=n,均可以轉(zhuǎn)化為 f(x)-n=0,
        此后就可以用牛頓迭代法，不斷逼近實際待求x值。
        牛頓迭代共識：f"(x_pre)x_pre+x_pre=x_cur
應(yīng)用: 迭代思想，類似于 動態(tài)規(guī)劃思想，pre==>cur，進(jìn)行動態(tài)推斷處理

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)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/42181.html

相關(guān)文章

LeetCode69. Sqrt(x) -- 求一個數(shù)的開方

摘要：牛頓迭代法的原理很簡單，其實是根據(jù)在附近的值和斜率，估計和軸的交點，因此牛頓迭代法的公式為其實就是求切線與軸的交點。代碼利用牛頓法進(jìn)行的更新，比直接從開始遍歷所作的循環(huán)要少牛頓迭代法的基本原理，請參考牛頓迭代法求開平方描述 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月技術(shù)文章匯總

摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運用場景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計工程在線診斷系統(tǒng)設(shè)計與實現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
【Leetcode】71. 簡化路徑

摘要：題目給定一個文檔的完全路徑，請進(jìn)行路徑簡化。例如，邊界情況你是否考慮了路徑的情況在這種情況下，你需返回。此外，路徑中也可能包含多個斜杠，如。文化和社會被恐懼所塑造，在將來這無疑也不會消失。題目給定一個文檔 (Unix-style) 的完全路徑，請進(jìn)行路徑簡化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 邊界情況:...

liuchengxu 2019-08-19 11:11 評論0 收藏0
【Leetcode】71. 簡化路徑

摘要：題目給定一個文檔的完全路徑，請進(jìn)行路徑簡化。例如，邊界情況你是否考慮了路徑的情況在這種情況下，你需返回。此外，路徑中也可能包含多個斜杠，如。文化和社會被恐懼所塑造，在將來這無疑也不會消失。題目給定一個文檔 (Unix-style) 的完全路徑，請進(jìn)行路徑簡化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 邊界情況:...

afishhhhh 2019-07-30 17:50 評論0 收藏0