x的平方根
實現(xiàn) int sqrt(int x) 函數(shù)。
計算并返回 x 的平方根汇鞭，其中 x 是非負整數(shù)凉唐。
由于返回類型是整數(shù)，結果只保留整數(shù)的部分霍骄，小數(shù)部分將被舍去台囱。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,
由于返回類型是整數(shù)，小數(shù)部分將被舍去读整。
題目分析
- 首先直接計算平方根不太現(xiàn)實簿训，所以這是一個在有序的1~x中查找出平方根的問題。
- 查找有序整數(shù)中的特定值绘沉，正常思路即二分查找煎楣，實現(xiàn)也簡單豺总。
-
遞歸縮小求解：
因此可以遞歸找到易解的小x车伞，然后再回溯整合到原x。
注意為什么選擇2作為系數(shù)進行遞歸呢喻喳？
——x縮小和放大2的倍數(shù)另玖，可以通過位操作實現(xiàn)，效率極高表伦。
遞歸式為：mySqrt(x)=mySqrt(x>>2)<<1
- 針對這個計算平方根的特定問題谦去，有 牛頓迭代法：
牛頓法（英語：Newton's method）又稱為牛頓-拉弗森方法（英語：Newton-Raphson method），它是一種在實數(shù)域和復數(shù)域上近似求解方程的方法蹦哼。方法使用函數(shù)
的泰勒級數(shù)的前面幾項來尋找方程的根鳄哭。
根據(jù)精度要求，和
收斂后差距小于1即可返回結果纲熏。
迭代求解示意：
迭代示意圖妆丘，圖源
(https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/)
如上圖所示锄俄，想求，圖示a=2
先隨便取xi=4勺拣，然后找到過(xi,yi)的切線奶赠，且的導數(shù)是
即切線方程
顯而易見這個切線與x軸的交點得
即得比
更接近解
。
牛頓迭代題解代碼
class Solution
{
public:
int mySqrt(int x)
{
//牛頓迭代
if(x<=1)
return x;
//注意long類型
long last=x/2;
long cur =(last+x/last)/2;
while(abs(last-cur)>=1)
{
last=cur;
cur=(cur +x/ cur) / 2.0 ;
if(cur<=x/cur)
return cur;
}
return cur;
}
};
