LeetCode-100題(Hot) 69. x 的平方根 [Java實作] [極速]

給你一個非負整數 x ，計算并傳回 x 的 平方根 。

由于傳回類型是整數，結果隻保留 整數部分 ，小數部分将被 舍去 。

注意：不允許使用任何内置指數函數和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

輸入：x = 4

輸出：2

本題可采用 牛頓疊代法

• 本題我們可以将其抽象成求方程  

  

   當 

  

   時的 >0 處的解。
• 結合牛頓疊代法，我們可以列出該曲線任意一點切線方程

  

    則其與 x軸交點 (y=0時) 為 

  

   此後我們僅需根據公式不斷更新x的值即可得到無限逼近 

  

   的目标值。
• 對于循環終止條件，僅需判斷兩次更新的x值間內插補點小于某一值 (例如 

  

   即可)

具體實作如下

public int mySqrt(int x) {
        if (x == 0) return 0;
        double C = x;
        double x0 = x;
        while (true) {
            double newX0 = 0.5 * (x0 + C/x0);
            if (Math.abs(x0-newX0) < 1e-7) {
                x0 = newX0;
                break;
            }
            x0 = newX0;
        }
        return (int) x0;
    }
           

                ​​​​​​​        

​​​​​​​