精华内容
下载资源
问答
  • 平方根,返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 class Solution { public int mySqrt(int x) { int l = 0; int r = x; int mid = 0; int res = 0; while(l<=r){ mid = (l+r)/2; if...

    一、平方根结果为整数

    求平方根,返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

    class Solution {
        public int mySqrt(int x) {
            int l = 0;
            int r = x;
            int mid = 0;
            int res = 0;
            while(l<=r){
                mid = (l+r)/2;
                if((long)mid*mid<=x){
                    res = mid;
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
            return res;
        }
    }
    

    二、平方根结果为小数

    class Solution {
    
    	public float fn(float n, float e) {//目标数字 和 精度
    		// 先求 e 的精度
    		String d = String.valueOf(e);
    		int lengh = d.length() - 2;
    		float x = 0;
    		if (n > 0 && e > 0) {
    			float low = 0;
    			float high = n;
    			while (low < high) {
    				// 二分,并控制精度
    				float mid = Float.parseFloat(String.format("%." + lengh + "f", (low + high) / 2));
    				if (mid * mid < n - e) {
    					low = mid;
    				} else if (mid * mid > n + e) {
    					high = mid;
    				} else {
    					x = mid;
    					break;
    				}
    			}
    		}
    		return x;
    	}
    }
    
    展开全文
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 解题思路 需要向上...
    实现 int sqrt(int x) 函数。
    计算并返回 x 的平方根,其中 x 是非负整数。
    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
    示例 1:
    输入: 4
    输出: 2
    示例 2:
    输入: 8
    输出: 2
    说明: 8 的平方根是 2.82842..., 
         由于返回类型是整数,小数部分将被舍去。
    
    

    解题思路

    需要向上取整

    class Solution:
        def mySqrt(self, x: int) -> int:
            if x == 0:
                return 0
    
            left = 1
            right = x // 2
    
            while left < right:
                # 注意:这里一定取右中位数,如果取左中位数,代码可能会进入死循环
                # mid = left + (right - left + 1) // 2
                mid = (left + right + 1) >> 1
                square = mid * mid
    
                if square > x:
                    right = mid - 1
                else:
                    left = mid
            # 因为一定存在,因此无需后处理
            return left
    
    

    当x为浮点数时,注意x在0 ~ 1之间的情况,这个时候结果不在0~x之间。

    import sys 
    # x is float
    # threshold 为边界阈值
    def mySqrt(x, threshold):
        if x>1:
            left, right = 0, x 
        else:
            # 当x小于1时,要注意边界条件,因为这时0~x之间任何数的平方都小于x,不可能达到条件
            left, right = 0, 1
        mid = (left + right) / 2 
        while  abs(mid*mid-x)>threshold:
            if mid*mid>x:
                right = mid 
            else:
                left = mid 
            mid = (left + right) / 2
        return mid 
            
    if __name__ == "__main__":
        print(mySqrt(4.0, 0.001))
        
    
    
    展开全文
  • x的平方根

    2020-10-03 10:21:42
    说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 袖珍计算器算法 「袖珍计算器算法」是一种用指数函数 exp 对数函数 ln 代替平方根函数方法。我们通过有限可以使用数学函数,得到...

    题目

    实现 int sqrt(int x) 函数。
    计算并返回 x 的平方根,其中 x 是非负整数。
    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

    示例 1:
    输入: 4
    输出: 2

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

    袖珍计算器算法

    「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数,得到我们想要计算的结果。
    在这里插入图片描述
    注意: 由于计算机无法存储浮点数的精确值(浮点数的存储方法可以参考 IEEE 754,这里不再赘述),而指数函数和对数函数的参数和返回值均为浮点数,因此运算过程中会存在误差。例如当 x = 2147395600 时,e^(1/2)lnx
    的计算结果与正确值 4634046340 相差 10^(−11),这样在对结果取整数部分时,会得到 4633946339 这个错误的结果。
    因此在得到结果的整数部分 ans 后,我们应当找出 ans 与 ans+1 中哪一个是真正的答案。

    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);
        }
    };
    

    复杂度分析

    时间复杂度:O(1),由于内置的 exp 函数与 log 函数一般都很快,我们在这里将其复杂度视为 O(1)。

    空间复杂度:O(1)。

    二分查找

    由于 x 平方根的整数部分 ans 是满足 k^2 ≤x 的最大 k 值,因此我们可以对 k进行二分查找,从而得到答案。
    二分查找的下界为 0,上界可以粗略地设定为 x。在二分查找的每一步中,我们只需要比较中间元素 mid 的平方与 x 的大小关系,并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算,不会存在误差,因此在得到最终的答案 ans 后,也就不需要再去尝试 ans+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 long)mid * mid <= x) 
                {
                    ans = mid;
                    l = mid + 1;
                } 
                else 
                {
                    r = mid - 1;
                }
            }
            return ans;
        }
    };
    

    复杂度分析

    时间复杂度:O(\log x)O(logx),即为二分查找需要的次数。

    空间复杂度:O(1)O(1)。

    牛顿迭代

    思路
    牛顿迭代法是一种可以用来快速求解函数零点的方法。
    为了叙述方便,我们用 C 表示待求出平方根的那个整数。显然,C 的平方根就是函数
    y = f(x) = x^2 - C
    的零点。

    牛顿迭代法的本质是借助泰勒级数,从初始值开始快速向零点逼近。我们任取一个 x0作为初始值,在每一步的迭代中,我们找到函数图像上的点 (xi,f(xi)),过该点作一条斜率为该点导数 f′(xi) 的直线,与横轴的交点记为 xi+1。xi+1
    相较于 xi 而言距离零点更近。在经过多次迭代后,我们就可以得到一个距离零点非常接近的交点。下图给出了从 x0 开始迭代两次,得到 x1 和 x2 的过程。
    在这里插入图片描述
    算法
    我们选择 x0=C 作为初始值。
    在每一步迭代中,我们通过当前的交点 xi,找到函数图像上的点 (xi,xi^2−C),作一条斜率为 f′(xi)=2xi 的直线,直线的方程为:
    在这里插入图片描述
    与横轴的交点为方程 2xix−(xi2+C)=0 的解,即为新的迭代结果 xi+1:
    在这里插入图片描述
    在进行 k 次迭代后,xk 的值与真实的零点 C^(1/2) 足够接近,即可作为答案。

    细节
    为什么选择 x0=C 作为初始值?
    在这里插入图片描述
    迭代到何时才算结束?

    每一次迭代后,我们都会距离零点更进一步,所以当相邻两次迭代得到的交点非常接近时,我们就可以断定,此时的结果已经足够我们得到答案了。一般来说,可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数 ϵ,其中 ϵ 一般可以取 10^-6 或 10 ^−7。

    如何通过迭代得到的近似零点得出最终的答案?
    在这里插入图片描述
    真正的零点为 n − 1/2ϵ,其中 n 是一个正整数,而我们迭代得到的结果为 n+1/2ϵ。在对结果保留整数部分后得到 n,但正确的结果为 n−1。

    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);
        }
    };
    

    复杂度分析

    时间复杂度:O(logx),此方法是二次收敛的,相较于二分查找更快。

    空间复杂度:O(1)。

    展开全文
  • // 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 // // 示例 1: // // 输入: 4 //输出: 2 // // // 示例 2: // // 输入: 8 //输出: 2 //说明: 8 的平方根是 2.82842..., // 由于返回类型是...

    1.x的平方根

    //实现 int sqrt(int x) 函数。 
    //
    // 计算并返回 x 的平方根,其中 x 是非负整数。 
    //
    // 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 
    //
    // 示例 1: 
    //
    // 输入: 4
    //输出: 2
    // 
    //
    // 示例 2: 
    //
    // 输入: 8
    //输出: 2
    //说明: 8 的平方根是 2.82842..., 
    //     由于返回类型是整数,小数部分将被舍去。
    // 
    // Related Topics 数学 二分查找

    x的平方根采用的是二分查找的方式,就是将原先的直接比较数组中的target和nums[i]换成了平方和数。

    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.爬楼梯

    //假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 
    //
    // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 
    //
    // 注意:给定 n 是一个正整数。 
    //
    // 示例 1: 
    //
    // 输入: 2
    //输出: 2
    //解释: 有两种方法可以爬到楼顶。
    //1.  1 阶 + 1 阶
    //2.  2 阶 
    //
    // 示例 2: 
    //
    // 输入: 3
    //输出: 3
    //解释: 有三种方法可以爬到楼顶。
    //1.  1 阶 + 1 阶 + 1 阶
    //2.  1 阶 + 2 阶
    //3.  2 阶 + 1 阶
    // 
    // Related Topics 动态规划

    这一题主要是要发现规律,后面的和前面的是什么关系,第n阶台阶=第n-1阶台阶+1或者第n-2阶台阶+2,就这样算出了一个迭代的式子,f(n)=f(n-1)+f(n-2)

    public int climbStairs(int n) {
            //通过规律我们可以防线,第n阶台阶可以看成是第n-1阶+1和第n-2阶+2,这两种
            //所以这是一个迭代式
            int r = 1, p=0, q=0;
            for (int i = 1; i <= n; i++) {
                p = q;
                q = r;
                r = p+q;
            }
            return r;
        }

     

    展开全文
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 二分查找 class ...
  • leetcode69 x 的平方根

    2021-05-07 13:16:06
    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 思路: 本题使用二分法...
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 解法一(二分法): ...
  • 由于返回类型是整数,结果只保留整数部分小数部分舍去。 问题解析: 本题我们可以使用C+STL内置函数库来实现sqrt(x)计算,然后再强制转换为int类型数据返回。 另外一种方式为:采用牛顿迭代方法来实现...
  • 由于x平方根的整数部分ans是满足k平方<=x的最大值,因此我们可以对k进行二分查找,求解答案。 二分查找的下界为0,上界可以粗略地设定为x。在二分查找的每一步中,我们只需要比较中间元素mid的平方与x的大小关系...
  • 69. x 的平方根

    2020-08-13 16:10:05
    题目: 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,...因此在得到结果的整数部分 res后,我们应当判断 resres+1中哪一个是真正的答案。 函
  • [Leetcode]x的平方根

    2020-10-09 10:22:44
    [Leetcode]x的平方根 ...说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 解题思路 袖珍计算器算法 「袖珍计算器算法」是一种用指数函数 exp⁡\expexp 对数函数 ln⁡\lnln 代替平
  • LeetCode 69. x 的平方根

    千次阅读 2021-03-11 15:48:30
    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 题解 下面这种方法...
  • #69. x的平方根

    2019-09-11 10:49:30
    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 知识点: 二分法:mid=...
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 ——题目...
  • &LeetCode69& x的平方根

    2020-02-20 18:21:52
    题目 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,...说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 来源:力扣(LeetCode) 思路 能想到方法就是算某值平方,然后去x比...
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 【思路分析】 ...
  • 力扣-69x的平方根

    2020-09-24 22:30:17
    说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 3.思路 二分查找,设置low=1, high=x,中间值为mid=low+(high-low)/2; 用x除mid,判断商值 mid==商, 返回商 mid > 商,置hig
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 解题思路: 取一个初始...
  • Leetcode69. x 的平方根

    2019-12-30 18:50:56
    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 题解: 方法一:二分法 时间复杂度:O(log⁡N),二分法时间复杂度是对数级别。 空间复杂度:O(1),使用了常数个数辅助空间用于存储比较。 ...
  • x 的平方根(二分法C语言实现)

    千次阅读 2019-04-26 21:26:30
    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 思路 首先设定左右边界...
  • 菜鸟成长逆袭之旅,爱好撸铁撸代码,有强制约束力,希望通过自己努力做一个高品质人 ...由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 ...
  • 算法之求x的平方根

    2021-01-31 00:15:59
    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 解析: 这题解法用暴力解法是非常简单。主要麻烦在于如何解更好,答案就是用牛顿迭代法。 下面这种方法可以很有效地求出根号 a近似值:...
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 2、解题思路 二分查找,逼近目标值 首先是边界情况:0、1 的平方根分别是 0、1。剩下就是 x >= 2 情况了。 左右指针指向左右边界,求出中位...
  • // 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 // // 示例 1: // // 输入: 4 //输出: 2 // // // 示例 2: // // 输入: 8 //输出: 2 //说明: 8 的平方根是 2.82842..., // 由于返回类型是...
  • 实现 int sqrt(int x) 函数。...说明: 8 的平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 思路: 暴力法:循环比较与与x大小,显然时间复杂度为o(n),但我们想想这似乎从有序列表里...
  • 1、二分搜索精髓: ... 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 这道题为什么可以使用二分法??? 解释:首先求x的平方根,即y^2 = x;即求y值,而该函数具有当调用性 ...
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 解题思路: 1.使用二分法,不断逼近x的平方根; 2.注意数据溢出时间超限问题,尽可能不让数据做乘法; 3.用除法来代替乘法,需要注意是x...
  • 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。 示例 1: 输入: 4 输出: 2 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 暴力for...
  • 并且请分别求包含整数部分的情况只看小数部分的情况。 例)2的平方根 :1.414213562373095048...(0~9全部出现需要19位) 思路 1.依次计算每个自然数的平方根 2.取出每个平方根的各个数位上的数字,并统计是否...

空空如也

空空如也

1 2 3 4 5
收藏数 92
精华内容 36
关键字:

平方根的整数部分和小数部分