69.x的平方根

落日映苍穹つ 2021-06-22 15:38 373阅读 0赞

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

*  思路1：二分法，前提x^2函数是单调递增的
 *  思路2：牛顿迭代法 3D游戏里面用到的求 1/sqrt(y)的方法

二分法

class Solution { 
    	public int mySqrt(int x) { 
    		if (x == 0 || x == 1) return x;
    		return doSqrt(x, 1);
    	}
    	//可以设定精度
    	public int doSqrt(int x, double precision) { 
    		int left = 0;
    		int right = x;
    		while (right - left > precision) { 
    			int mid = (left + right) /2;
    			if (mid == x / mid) {   // mid * mid == x 当数值大会越界
    				return mid;
    			} else if (mid > x / mid) { 
    				right = mid;
    			} else { 
    				left = mid;
    			}
    		}
    		return left;
    	}
    }

牛顿迭代法，不过这里x会出现越界问题，这里我就强转为long，最后由强转为int，在int里面不会有问题

class Solution { 
    	public int mySqrt(int x) { 
    		if (x == 0 || x == 1) return x;
    		long x1 = (long)x;
    		long r = x1;
    		while (r > x1/r) { 
    			r = (r + x1 / r) / 2;
    		}
    		return (int)r;
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，373人围观）

还没有评论，来说两句吧...

相关阅读

相关 69. x 的平方根

69. x 的平方根给你一个非负整数 x ，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。注意：不允许使用

r囧r小猫/ 2024年04月01日 15:44/ 0 赞/ 44 阅读

相关 69. x 的平方根

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

雨点打透心脏的1/2处/ 2023年01月23日 14:57/ 0 赞/ 13 阅读

相关 LeetCode 69. x 的平方根

69. x 的平方根 [https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-lee

亦凉/ 2022年11月07日 05:53/ 0 赞/ 134 阅读

相关 leetcode69x的平方根

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

约定不等于承诺〃/ 2022年10月08日 13:22/ 0 赞/ 196 阅读

相关 Leetcode 69. x 的平方根

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

古城微笑少年丶/ 2022年09月05日 15:44/ 0 赞/ 174 阅读

相关 69. x 的平方根

[https://leetcode-cn.com/problems/sqrtx/][https_leetcode-cn.com_problems_sqrtx] 难度简单749

￡神魔★判官ぃ/ 2022年09月05日 04:04/ 0 赞/ 154 阅读

相关 leetcode:69. x 的平方根

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

电玩女神/ 2022年04月10日 03:56/ 0 赞/ 262 阅读

相关 LeetCode 69. x 的平方根

1. x 的平方根题目实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。

深碍√TFBOYSˉ_/ 2022年03月26日 14:48/ 0 赞/ 248 阅读

相关 leetcode 69. x 的平方根

69. x 的平方根 > 难度：简单 > > 题库地址：[leetcode-cn.com/problems/sq…][leetcode-cn.com_problems_

灰太狼/ 2022年01月20日 11:59/ 0 赞/ 230 阅读

相关 69.x的平方根

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

落日映苍穹つ/ 2021年06月22日 15:38/ 0 赞/ 374 阅读