乐趣区

关于leetcode:leetcode-69-Sqrtx-x-的平方根简单

一、题目粗心

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 保持一天一道题,明天阴天
退出移动版