69. Sqrt(x)

題目

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

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

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

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

例子：

思路：

這題最先想到的是暴力法（習慣了），后來想想這種暴力解決的之前做過，用二分法效率高，大概就是正常二分找，因為返回的是整數，所以直接返回left的值，這里要注意的是中間不能用乘法，會溢出，用除法就不會溢出很關鍵！

代碼：

public int mySqrt(int x) {// 特殊值判斷if (x == 0) {return 0;}if (x == 1) {return 1;}int left = 1;int right = x;while (left < right) {int mid = left + (right - left + 1) / 2;if (mid *mid > x ) {right = mid - 1;} else {left = mid;}}return left;}

總結

很常規的一題二分法，其實想想二分用的真的挺多的，之前看過一個模板，二分的模板很強大，LeetCode上有，有興趣的可以搜一下！

2021年9月28日17:38:08

總結

以上是生活随笔為你收集整理的LetCode#69（JAVA）给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去.的全部內容，希望文章能夠幫你解決所遇到的問題。

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