每天一道LeetCode-----重新实现开方运算sqrt(x)，只返回整数部分即可

Sqrt(x)

原题链接Sqrt(x)

重新实现开方运算。

因为要求实现的开方运算只需要返回整数部分即可，所以首先考虑一下当n为多少时可以返回。
n是给定x的开方结果一定满足

• n * n <= x
• (n + 1) * (n + 1) > x

所以可以从这两点入手，同时，因为结果可以是[1, x]范围任意一个数字，所以可以利用二分法加快执行速率

代码如下

class Solution { public:int mySqrt(int x) {int low = 0;int high = x;while(low < high){/* 这里最好用low + (high - low) / 2计算中位数，否则low + high容易溢出 *//* 另外middle最好是long long int类型，因为middle * middle也容易溢出 */long long int middle = low + (high - low) / 2;if(middle * middle <= x && (middle + 1) * (middle + 1) > x)return middle;else if(middle * middle > x)high = middle - 1;elselow = middle + 1;}return low;} };

总结

以上是生活随笔为你收集整理的每天一道LeetCode-----重新实现开方运算sqrt(x)，只返回整数部分即可的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。