力扣面试150 x 的平方根 二分 换底法 牛顿迭代法 一题多解

Problem: 69. x 的平方根

思路

👨‍🏫 参考题解

💖 袖珍计算器算法

class Solution {public int mySqrt(int x){if (x == 0)return 0;
//		Math.exp(3)：e的三次方int ans = (int) Math.exp(0.5 * Math.log(x));return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;//处理 10的-11次方 的误差}
}

💖 二分解法

class Solution {
//	二分查找法
//	二分查找法public int mySqrt(int x){long l = 0;long r = x;while (l < r){long m = l + r + 1 >> 1
//			long m = l + (r - l + 1) / 2;if (m * m > x)r = m - 1;elsel = m;}return (int) l;}
}

💖 牛顿迭代法

👨‍🏫 参考题解

class Solution {public int mySqrt(int a) {long x = a;while (x * x > a) x = (x + a / x) / 2;return (int)x;}
}