LeetCode 69. x 的平方根

简介: LeetCode 69. x 的平方根

69. x 的平方根


https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/


实现 int sqrt(int x) 函数。


计算并返回 x 的平方根,其中 x 是非负整数。


由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。


示例 1:


输入: 4
输出: 2


示例 2:


输入: 8
输出: 2


说明: 8 的平方根是 2.82842…,由于返回类型是整数,小数部分将被舍去。


题解


方法一:牛顿迭代法


下面这种方法可以很有效地求出根号 aa 的近似值:首先随便猜一个近似值 xx,然后不断令 xx 等于 xx 和 a/xa/x 的平均数,迭代个六七次后 xx 的值就已经相当精确了。


例如,我想求根号 22 等于多少。假如我猜测的结果为 44,虽然错的离谱,但你可以看到使用牛顿迭代法后这个值很快就趋近于根号 22 了:


( 4 + 2/ 4 ) / 2 = 2.25


( 2.25 + 2/ 2.25 ) / 2 = 1.56944…


( 1.56944…+ 2/1.56944…) / 2 = 1.42189…


( 1.42189…+ 2/1.42189…) / 2 = 1.41423…


….


如果所示:




代码


(ps:一开始不要脸的写了个math中的 sqrt函数 看了大佬写的题解,感觉几年数学白学 T^T)


class Solution {
public:
    int s;
    int mySqrt(int x) {
        s=x;
        if(x==0) 
            return 0;
        return ((int)(Sqrt(x)));
    }
    double Sqrt(double x){
        double res=(x+s/x)/2;
        if(res==x)
            return x;
        else
            return Sqrt(res);
    }
};


简写:


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


方法二:二分法



int mySqrt(int a) {
  if (a == 0) 
    return a;
  int l = 1, r = a, mid, sqrt;
  while (l <= r) {
    mid = l + (r - l) / 2;
    sqrt = a / mid;
    if (sqrt == mid) {
      return mid;
    } else if (mid > sqrt) {
      r = mid - 1;
    } else {
      l = mid + 1;
    } 
  }
  return r;
}


相关文章
|
2天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
6天前
|
SQL 算法 数据可视化
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
|
10天前
|
算法 Java Go
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
6 1
|
1月前
【力扣】69. x 的平方根
【力扣】69. x 的平方根
|
8月前
【Leetcode-67. 二进制求和-69.x的平方根】
【Leetcode-67. 二进制求和-69.x的平方根】
25 0
|
1月前
leetcode-69:x 的平方根
leetcode-69:x 的平方根
37 0
|
9月前
|
存储
leetcode:69. x 的平方根
利用二分查找思想,在0与x区间进行查找。 设置左边界 left (初始值为0),右边界 right(初始值为x)和中值 mid (值为区间的中间值),同时设置一个ans(初始值为-1)作为最终返回值。
59 0
YI
|
11月前
|
Go
LeetCode 0069. X的平方根【Go】
LeetCode 0069. X的平方根【Go】
YI
67 0
|
Java Python
leetcode.69:x的平方根
leetcode.69:x的平方根
60 0
力扣69x的平方根
力扣69x的平方根
41 0