一、题目粗心
https://leetcode.cn/problems/sqrtx
标签: 查找
给你一个非负整数 x,计算并返回 x 的 算术平方根。
因为返回类型是整数,后果只保留 整数局部,小数局部将被 舍去。
留神:不容许应用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5。
示例 1:
输出:x = 4
输入:2
示例 2:
输出:x = 8
输入:2
解释:8 的算术平方根是 2.82842…, 因为返回类型是整数,小数局部将被舍去。
提醒:
-
0 <= x <= 231 – 1
二、解题思路
两个思路:
二分法:sqrt = a / mid,判断 sqrt == mid
牛顿迭代法:x = (x x/a)/2,判断 x x > a三、解题办法
3.1 Java 实现 - 二分法
public class Solution2 {public int mySqrt(int a) { // 留神:独自思考 0,避免除以 0 的状况 if (a == 0) {return 0;} int left = 1; int right = a; int mid; int sqrt; // 留神:条件是 <= while (left <= right) { // 留神:这样写能够避免溢出 mid = left + (right - left) / 2; sqrt = a / mid; if (sqrt == mid) { // 间接返回,mid 就是平方根 return mid; } else if (mid > sqrt) {right = mid - 1;} else {left = mid + 1;} } return right; } }
3.2 Java 实现 - 牛顿迭代法
public class Solution {public int mySqrt(int a) { // 避免 int 越界,用 long 来存储乘法后果 long x = a; while (x * x > a) {x = (x + a / x) / 2; } return (int) x; } }
四、总结小记
- 2022/5/25 保持一天一道题,明天阴天