Leetcode

LeetCode 69. Sqrt（x）xの平方根（Java）



Leetcode 69 Square Root Sqrt X



トピック：

int sqrt（int x）を実装します。

xの平方根を計算して返します。ここで、xは負でない整数であることが保証されています。



戻り値の型は整数であるため、10進数は切り捨てられ、結果の整数部分のみが返されます。

例1：
入力：4
出力：2



例2：
入力：8
出力：2
説明：8の平方根は2.82842…であり、
小数部は切り捨てられ、2が返されます。

回答：

解決策1：二分法を使用する
class Solution { public int mySqrt(int x) { int start=1 int end=x while(start<=end){ int middle=(start+end)/2 if(middle==x/middle){ return middle }else if(middle>x/middle){ end=middle-1 }else{ start=middle+1 } } return end } }

二分法を使用するときは、オーバーフローの原因となる中央の正方形に注意してください。 （最初の提出など）
200

解決策2：ニュートン反復法
class Solution { public int mySqrt(int x) { if(x<=1){ return x } double r=1 while(Math.abs(r*r-x)>0.00001){ r=(r+x/r)/2 } return (int)r } }

問題の本質は、平方根を見つけること、つまりx ^ 2 = tを解くことです。
関数f（x）= x ^ 2- tを設定し、f（x）= 0とすると、解xはtの平方根であり、図のX軸との交点として表されます。最後に、この交差点を要求します
画像の初期点（X0、f（X0））を取り、それを接線にします。接線とX軸の交点はX1で、次に（X1、f（X1））接線、そして最後に接線とX軸の交点はの交点に無限に近づきます。 f（x）= 0。
最後に、再帰方程式が得られます：X [i +] =（X [i] + t / X [i]）/ 2
画像