网站代码如何导入,深圳cms建站模板,规模以上工业企业如何认定,wordpress招商模板下载每日一题(LeetCode)----二分查找#xff08;三#xff09;
1.题目#xff08;69. x 的平方根 #xff09;
给你一个非负整数 x #xff0c;计算并返回 x 的 算术平方根 。
由于返回类型是整数#xff0c;结果只保留 整数部分 #xff0c;小数部分将被 舍去 。
**注意…每日一题(LeetCode)----二分查找三
1.题目69. x 的平方根
给你一个非负整数 x 计算并返回 x 的 算术平方根 。
由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。
**注意**不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1
输入x 4
输出2示例 2
输入x 8
输出2
解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。提示
0 x 231 - 1
2.解题思路
思路一 二分
利用二分的思想二分的范围最开始就是从0开始到目标数结束
然后我们进行二分如果我们找到的数的平方比目标数小那么我们的答案为当前找到的数然后二分范围的左边界找到的当前数右边的位置继续进行二分
如果我们如果我们找到的数的平方比目标数大那么二分范围的右边界变为找到的当前数左边的位置继续进行二分
直到左边界比右边界大了结束操作
思路二 袖珍计算器算法来源于牛客官方解答 思路三 牛顿迭代来源于牛客官方解答 3.代码
思路一的代码
class Solution {
public:int mySqrt(int x) {int left0;int rightx;int ans-1;while(leftright){long long midleft(right-left)/2;if(mid*midx){ansmid;leftmid1;}if(mid*midx){rightmid-1;}}return ans;}
};思路二的代码
class Solution {
public:int mySqrt(int x) {if (x 0) {return 0;}int ans exp(0.5 * log(x));return ((long long)(ans 1) * (ans 1) x ? ans 1 : ans);}
};作者力扣官方题解
链接https://leetcode.cn/problems/sqrtx/
来源力扣LeetCode思路三的代码
class Solution {
public:int mySqrt(int x) {if (x 0) {return 0;}double C x, x0 x;while (true) {double xi 0.5 * (x0 C / x0);if (fabs(x0 - xi) 1e-7) {break;}x0 xi;}return int(x0);}
};作者力扣官方题解
链接https://leetcode.cn/problems/sqrtx/
来源力扣LeetCode
