淘宝网站开发源码,个性化网站有哪些,软文范例100例,本地的唐山网站建设【问题描述】
实现 int sqrt(int x) 函数。计算并返回 x 的平方根#xff0c;其中 x 是非负整数。由于返回类型是整数#xff0c;结果只保留整数的部分#xff0c;小数部分将被舍去。输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数#xff0c;小数部…【问题描述】
实现 int sqrt(int x) 函数。计算并返回 x 的平方根其中 x 是非负整数。由于返回类型是整数结果只保留整数的部分小数部分将被舍去。输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。
【解答思路】
1. 二分法面试必备
1.1 缩小边界 x/2 时间复杂度O(logN) 空间复杂度O(1) Java 代码要注意到如果中点 mid 声明为 int 类型针对大整型测试用例通不过因此变量需要声明为 long 类型。 public class Solution {public int mySqrt(int x) {// 注意针对特殊测试用例例如 2147395599// 要把搜索的范围设置成长整型// 为了照顾到 0 把左边界设置为 0long left 0;// # 为了照顾到 1 把右边界设置为 x // 2 1long right x / 2 1;while (left right) {// 注意这里一定取右中位数如果取左中位数代码会进入死循环// long mid left (right - left 1) / 2;long mid (left right 1) 1;long square mid * mid;//画图排除法思想 现象最简单的 if (square x) {right mid - 1;} else {left mid;}}// 因为一定存在因此无需后处理return (int) left;}}
1.2 常规思路 零神笔法
时间复杂度O(logN) 空间复杂度O(1)
class Solution {public int mySqrt(int x) {int l 0, r x, ans -1;while (l r) {int mid l (r - l) / 2;if ((long)mid * mid x) {ans mid;l mid 1;}else {r mid - 1;}}return ans;}
}
2.牛顿法
牛顿法得到的是平方根的浮点型精确值可能会有一定误差根据题目中的要求把最后得到的这个数转换为 int 型即去掉小数部分即可 时间复杂度O(logN) 空间复杂度O(1)
public class Solution {public int mySqrt(int a) {long x a;while (x * x a) {x (x a / x) / 2;}return (int) x;}
}
3. 袖珍计算器算法 零神提供新思路 时间复杂度O(logN) 空间复杂度O(1)
class Solution {public int mySqrt(int x) {if (x 0) {return 0;}int ans (int)Math.exp(0.5 * Math.log(x));return (long)(ans 1) * (ans 1) x ? ans 1 : ans;}
}
4. 库函数 皮一下很开心
public int mySqrt(int x) {return (int)Math.sqrt(x);}【总结】
1. 一题多解 乐趣多
2.二分法 注意细节
3. 一人之下 真好看
参考链接https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/ 参考链接https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/
