文章目錄

• • 1. 題目
  • 2.解題
  • • 2.1 二分查找
    • 2.2 牛頓迭代

1. 題目

實現 int sqrt(int x) 函數。

計算并返回 x 的平方根，其中 x 是非負整數。

由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。

示例 1:輸入: 4 輸出: 2 示例 2:輸入: 8 輸出: 2 說明: 8 的平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/sqrtx
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2.解題

2.1 二分查找

• 二分查找
  

class Solution { public:int mySqrt(int x) {if(x <= 1)return x;double left = 1, right = x/2+1, mid;while(right-left > 0.00001){mid = (left+right)/2;if(mid*mid > x)right = mid;elseleft = mid;}return floor(right);} };

2.2 牛頓迭代

class Solution { public:int mySqrt(int x) {if(x <= 1)return x;double x0 = x, x1, c = x;while(1){x1 = 0.5*(c/x0 + x0);if(fabs(x0-x1) < 1e-6)break;x0 = x1;}return x0;} };

總結

以上是生活随笔為你收集整理的LeetCode 69. x 的平方根（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。