当前位置: 首页 > news >正文

leetcode69--x的平方根

方法一

直接进行简单的循环遍历,找到符合条件的值返回结果即可

class Solution {public int mySqrt(int x) {for (int i = 0; i <= x; i++) {if ((long)i * i <= x && (long)(i + 1) * (i + 1) > x) {return i;}}return -1; // 这个返回值实际上不会被触发,因为对于所有正整数 x,总会找到一个 i}
}

二分查找法

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

详细解析

  1. 初始化变量

    • left 初始化为 0,表示搜索区间的左边界。
    • right 初始化为 x,表示搜索区间的右边界。
    • res 初始化为 -1,用于存储最终的结果。
  2. 二分查找循环

    • 使用 while (left <= right) 循环,直到 left 超过 right 为止。
    • 在每次迭代中,计算中间值 mid
      int mid = left + (right - left) / 2;
      
      这种计算方式是为了防止 (left + right) / 2 可能导致的整数溢出问题。
  3. 检查中间值

    • 计算 mid * mid 并与 x 进行比较。为了避免整数溢出,将 mid * mid 转换为 long 类型:
      if ((long)mid * mid <= x) {res = mid;left = mid + 1;
      } else {right = mid - 1;
      }
      
    • 如果 mid * mid 小于或等于 x,说明 mid 是一个可能的解,更新 resmid,并将 left 移动到 mid + 1,继续在右半部分查找更大的可能解。
    • 如果 mid * mid 大于 x,说明 mid 太大了,需要在左半部分查找更小的解,因此将 right 移动到 mid - 1
  4. 返回结果

    • left 超过 right 时,循环结束,此时 res 存储的就是 x 的平方根(向下取整)。

http://www.mrgr.cn/news/40864.html

相关文章:

  • 图文深入理解Oracle Network配置管理(一)
  • Qt 中的 QListWidget、QTreeWidget 和 QTableWidget:简化的数据展示控件
  • 计算机毕业设计 基于协同过滤算法的个性化音乐推荐系统的设计与实现 Java实战项目 附源码+文档+视频讲解
  • 基于 QAnything 的知识库问答系统:技术解析与应用实践
  • WebRTC Connection Negotiate解决
  • go+redis基于tcp实现聊天室
  • Redis实现每日签到(大数据量)
  • Java之方法的使用
  • 端到端如火如荼, 传统规划控制还有前途吗?
  • Linux系统命令:用于改变用户的登录 Shell 的命令chsh命令详解
  • 有没有免费写论文的软件?推荐这5款
  • 深耕领域、拓宽视野与培养软技能
  • C++语言学习(2): name lookup 的概念
  • 面试题1-fail-safe机制与fail-fast 机制
  • JavaScript Set基础与实战应用
  • 使用容器启动的zk无法暴露3888问题解决
  • 您的计算机已被Lockbit3.0勒索病毒感染?恢复您的数据的方法在这里!
  • 【论文阅读】基于真实数据感知的模型功能窃取攻击
  • 内存对齐的原理和使用
  • 使用 Docker 制作 YashanDB 镜像:深度解析与实战指南