模块三:二分——69.x的平方根

2024-04-24 02:36
文章标签 模块 二分 69 平方根

本文主要是介绍模块三:二分——69.x的平方根,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目描述
  • 算法原理
    • 解法一:暴力查找
    • 解法二:二分查找
  • 代码实现
    • 暴力查找
    • C++
    • Java

题目描述

题目链接:69.x的平方根
在这里插入图片描述

算法原理

解法一:暴力查找

依次枚举 [0, x] 之间的所有数 i (这⾥没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回了,往后的情况就不会再判断。反⽽研究枚举区间,既耽误时间,⼜可能出错)

  • 如果 i * i == x ,直接返回 x ;
  • 如果 i * i > x ,说明之前的⼀个数是结果,返回 i - 1 。

由于 i * i 可能超过 int 的最⼤值,因此使⽤ long long 类型

解法二:二分查找

设 x 的平⽅根的最终结果为 index ,分析 index 左右两边区间数据的特点:

  • [0, index] 之间的元素,平⽅之后都是⼩于等于 x 的;
  • [index + 1, x] 之间的元素,平⽅之后都是⼤于 x 的。

因此可以使⽤⼆分查找算法。

代码实现

暴力查找

class Solution {
public:int mySqrt(int x) {// 由于两个较⼤的数相乘可能会超过 int 最⼤范围// 因此⽤ long longlong long i = 0;for (i = 0; i <= x; i++) {// 如果两个数相乘正好等于 x,直接返回 iif (i * i == x)return i;// 如果第⼀次出现两个数相乘⼤于 x,说明结果是前⼀个数if (i * i > x)return i - 1;}// 为了处理oj题需要控制所有路径都有返回值return -1;}
};

C++

class Solution {
public:int mySqrt(int x) {// 处理边界情况if (x < 1)return 0;// 二段性使用二分int left = 1, right = x;while (left < right) {// 防溢出long long mid = left + (right - left + 1) / 2;if (mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};

Java

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

这篇关于模块三:二分——69.x的平方根的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/930540

相关文章

Python使用date模块进行日期处理的终极指南

《Python使用date模块进行日期处理的终极指南》在处理与时间相关的数据时,Python的date模块是开发者最趁手的工具之一,本文将用通俗的语言,结合真实案例,带您掌握date模块的六大核心功能... 目录引言一、date模块的核心功能1.1 日期表示1.2 日期计算1.3 日期比较二、六大常用方法详

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时

Node.js net模块的使用示例

《Node.jsnet模块的使用示例》本文主要介绍了Node.jsnet模块的使用示例,net模块支持TCP通信,处理TCP连接和数据传输,具有一定的参考价值,感兴趣的可以了解一下... 目录简介引入 net 模块核心概念TCP (传输控制协议)Socket服务器TCP 服务器创建基本服务器服务器配置选项服

Python利用自带模块实现屏幕像素高效操作

《Python利用自带模块实现屏幕像素高效操作》这篇文章主要为大家详细介绍了Python如何利用自带模块实现屏幕像素高效操作,文中的示例代码讲解详,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、获取屏幕放缩比例2、获取屏幕指定坐标处像素颜色3、一个简单的使用案例4、总结1、获取屏幕放缩比例from

nginx-rtmp-module模块实现视频点播的示例代码

《nginx-rtmp-module模块实现视频点播的示例代码》本文主要介绍了nginx-rtmp-module模块实现视频点播,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录预置条件Nginx点播基本配置点播远程文件指定多个播放位置参考预置条件配置点播服务器 192.

多模块的springboot项目发布指定模块的脚本方式

《多模块的springboot项目发布指定模块的脚本方式》该文章主要介绍了如何在多模块的SpringBoot项目中发布指定模块的脚本,作者原先的脚本会清理并编译所有模块,导致发布时间过长,通过简化脚本... 目录多模块的springboot项目发布指定模块的脚本1、不计成本地全部发布2、指定模块发布总结多模

Python中构建终端应用界面利器Blessed模块的使用

《Python中构建终端应用界面利器Blessed模块的使用》Blessed库作为一个轻量级且功能强大的解决方案,开始在开发者中赢得口碑,今天,我们就一起来探索一下它是如何让终端UI开发变得轻松而高... 目录一、安装与配置:简单、快速、无障碍二、基本功能:从彩色文本到动态交互1. 显示基本内容2. 创建链

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

python中的与时间相关的模块应用场景分析

《python中的与时间相关的模块应用场景分析》本文介绍了Python中与时间相关的几个重要模块:`time`、`datetime`、`calendar`、`timeit`、`pytz`和`dateu... 目录1. time 模块2. datetime 模块3. calendar 模块4. timeit

Python模块导入的几种方法实现

《Python模块导入的几种方法实现》本文主要介绍了Python模块导入的几种方法实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录一、什么是模块?二、模块导入的基本方法1. 使用import整个模块2.使用from ... i