当前位置:   article > 正文

LeetCode69 x的平方根

LeetCode69 x的平方根
  1. 题目
    1. 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
    2. 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

  2. 示例
    1. 示例 1
    2. 输入:x = 4
    3. 输出:2
    4. 示例 2
    5. 输入:x = 8
    6. 输出:2
    7. 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

  3. 解题思路
    1. 方法一:二分查找。可以是用二分查找的思想,来查找x的平方根。
      1. x的平方根一定小于等于x / 2,减少查询范围。
      2. 左边界为1, 有边界为x / 2.
    2. 方法二:牛顿迭代法
  4. 代码(Java)
    1. // 方法一
    2. class Solution {
    3. public int mySqrt(int x) {
    4. if (x == 1) {
    5. return 1;
    6. }
    7. long a = x;
    8. long left = 1;
    9. long right = a / 2;
    10. long mid = 0;
    11. while (left <= right) {
    12. mid = (left + right) / 2;
    13. if (mid * mid == a) {
    14. return (int) mid;
    15. } else if (mid * mid > a) {
    16. right = mid - 1;
    17. } else {
    18. left = mid + 1;
    19. }
    20. }
    21. return (int) right;
    22. }
    23. }
    1. class Solution {
    2. public int mySqrt(int x) {
    3. if (x == 1) {
    4. return 1;
    5. }
    6. double i = 0;
    7. int k = 0;
    8. double m = x;
    9. while ((i * i) <= m)
    10. i += 0.1;
    11. for (int j = 0; j < 10; j++) {
    12. i = (m / i + i) / 2;
    13. }
    14. return (int) i;
    15. }
    16. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/243521
推荐阅读
相关标签
  

闽ICP备14008679号