每日一题(LeetCode)----二分查找(三)
每日一题(LeetCode)----二分查找(三)
1.题目(69. x 的平方根 )
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
**注意:**不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 231 - 1
2.解题思路
思路一: 二分
利用二分的思想,二分的范围最开始就是从0开始到目标数结束
然后我们进行二分,如果我们找到的数的平方比目标数小,那么我们的答案为当前找到的数,然后二分范围的左边界找到的当前数右边的位置,继续进行二分
如果我们如果我们找到的数的平方比目标数大,那么二分范围的右边界变为找到的当前数左边的位置,继续进行二分
直到左边界比右边界大了,结束操作
思路二: 袖珍计算器算法(来源于牛客官方解答)

思路三: 牛顿迭代(来源于牛客官方解答)



3.代码
思路一的代码:
class Solution {
public:int mySqrt(int x) {int left=0;int right=x;int ans=-1;while(left<=right){long long mid=left+(right-left)/2;if(mid*mid<=x){ans=mid;left=mid+1;}if(mid*mid>x){right=mid-1;}}return ans;}
};
思路二的代码:
class Solution {
public:int mySqrt(int x) {if (x == 0) {return 0;}int ans = exp(0.5 * log(x));return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);}
};作者:力扣官方题解
链接:https://leetcode.cn/problems/sqrtx/
来源:力扣(LeetCode)
思路三的代码:
class Solution {
public:int mySqrt(int x) {if (x == 0) {return 0;}double C = x, x0 = x;while (true) {double xi = 0.5 * (x0 + C / x0);if (fabs(x0 - xi) < 1e-7) {break;}x0 = xi;}return int(x0);}
};作者:力扣官方题解
链接:https://leetcode.cn/problems/sqrtx/
来源:力扣(LeetCode)
相关文章:
每日一题(LeetCode)----二分查找(三)
每日一题(LeetCode)----二分查找(三) 1.题目(69. x 的平方根 ) 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。 **注意…...
使用 TensorFlow FasterRCNN 网络进行目标检测
目录 描述 此示例的工作原理 处理输入图形 数据准备 sampleUffFasterRCNN 插件 验证输出 TensorRT API 层和操作 TensorRT API 层和操作 先决条件 运行示例 示例 --help 选项 附加资源 许可 变更记录 已知问题 本示例,sampleUffFasterRCNN࿰…...
数据结构——顺序表(SeqList)
目录 1. 顺序表介绍 2. 顺序表工程 2.1 顺序表定义 2.1.1 静态顺序表 2.1.2 动态顺序表 2.2顺序表接口 2.2.1 顺序表初始化 2.2.2 顺序表打印 2.2.3 顺序表销毁 2.2.4 顺序表数据插入 2.2.4.1 容量检查 2.2.4.2 顺序表尾插 2.2.4.3 顺序表头插 2.2.4.4 顺序表随机…...
Uni-App 快捷登录
uniapp 实现一键登录前置条件: 开通uniCloud, 开通一键登录功能参考的文档 : 官网 - 一键登录uniapp指南 : https://uniapp.dcloud.net.cn/univerify.html#%E6%A6%82%E8%BF%B0 官网 - 一键登录开通指南 : https://ask.dcloud.net.cn/article/37965 官网 - unicloud使用指南 htt…...
DbUtils + Druid 实现 JDBC 操作 --- 附BaseDao
文章目录 Apache-DBUtils实现CRUD操作1 Apache-DBUtils简介2 主要API的使用2.1 DbUtils2.2 QueryRunner类2.3 ResultSetHandler接口及实现类 3 JDBCUtil 工具类编写3.1 导包3.2 编写配置文件3.3 编写代码 4 BaseDao 编写 Apache-DBUtils实现CRUD操作 1 Apache-DBUtils简介 com…...
css:元素居中整理水平居中、垂直居中、水平垂直居中
目录 1、水平居中1.1、行内元素1.2、块级元素 2、垂直居中2.1、单行文字2.2、多行文字2.3、图片垂直居中 3、水平垂直居中参考文章 1、水平居中 1.1、行内元素 行内元素(比如文字,span,图片等)的水平居中,其父元素中…...
从零开始的目标检测和关键点检测(二):训练一个Glue的RTMDet模型
从零开始的目标检测和关键点检测(二):训练一个Glue的RTMDet模型 一、config文件解读二、开始训练三、数据集分析四、ncnn部署 从零开始的目标检测和关键点检测(一):用labelme标注数据集 从零开始的目标检测…...
React18新特性?
文章目录 前言Automatic BatchingTransitionsSuspenseNew Hooks后言 前言 hello world欢迎来到前端的新世界 😜当前文章系列专栏:react.js 🐱👓博主在前端领域还有很多知识和技术需要掌握,正在不断努力填补技术短板。…...
筹码博弈K线长阳选股公式,穿越筹码密集区
普通K线是由最高价、开盘价、最低价、收盘价四个价格构成的,而博弈K线是以这个四个价格对应的获利盘构成K线,反映筹码的获利情况。把鼠标移动到K线上,停留在对应的价格,就可以在右侧的筹码分布图看到相应的获利盘数据。࿰…...
微服务设计模式-架构真题(六十八)
UNIX的源代码控制工具(Source Code control System,SCCS)是项目开发中常用的()。 源代码静态分析工具文档分析工具版本控制工具再工程工具 答案:C 解析: SCCS是版本控制工具 网闸的描述错误的是()。 双…...
LeetCode----52. N 皇后 II
题目 n 皇后问题 研究的是如何将 n 个皇后放置在 n n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。 示例 1: 输入:n = 4 输出:2 解释:如上图所示,4 皇后问题存在两个不同的解法。 示例 2: 输入:n = …...
解决pycharm中,远程服务器上文件找不到的问题
一、问题描述 pycharm中,当我们连接到远程服务器上时。编译器中出现报错问题: cant open file /tmp/OV2IRamaar/test.py: [Errno 2] No such file or directory 第二节是原理解释,第三节是解决方法。 二、原理解释 实际上这是由于我们没有设置…...
虹科荣誉 | 喜讯!虹科成功入选“广州首届百家新锐企业”!!
文章来源:虹科品牌部 阅读原文:虹科荣誉 | 喜讯!虹科成功入选“广州首届百家新锐企业”!! 近日,由中共广州市委统战部、广州市工商业联合会、广州市工业和信息化局、广州市人民政府国有资产监督管理委员会…...
如何利用Jmeter从0到1做一次完整的压测?这2个步骤很关键!
压测,在很多项目中都有应用,是测试小伙伴必备的一项基本技能,刚好最近接手了一个小游戏的压测任务,一轮压测下来,颇有收获,赶紧记录下来,与大家分享一下,希望大家能少踩坑。 一、压…...
基于STM32+微信小程序设计的智能门锁(4种开锁方式)_2023
一、项目介绍 1.1 项目背景 随着智能家居的普及,智能门锁作为一个非常重要的组成部分,受到了人们越来越多的关注。传统的机械锁门禁已经不能满足人们对于门锁安全、便捷性和智能化的需求,因此市场对于智能门锁的需求不断增加。而随着技术的发展,基于单片机的智能门锁已经…...
享受户外的美好时光:花园吊椅的魅力
拥有舒适的花园吊椅,就像在家中创造了一个度假天堂。这些轻松摇摆的座位为您提供了一个完美的地方,既能舒适躺卧,又能让您在家中的花园或庭院中感受到度假的氛围。度过美好时光的吊椅,将成为家庭花园的一大亮点,为您带…...
游戏中找不到d3dx9_43.dll怎么办,教你快速解决方法
在计算机的世界里,我们经常会遇到一些让人头疼的问题。比如,有一天,小明正在玩他最喜欢的游戏,突然弹出了一个错误提示:“由于找不到d3dx9_43.dll,无法继续执行代码”。小明感到非常困惑,不知道这是什么意思…...
蓝桥杯:买不到的数目
对于两个互质的正整数 n , m n,m n,m,请找出来不能被 n n n和 m m m组成的最大数 X X X 例如:对于4,7那么 X X X17,因为对于大于17的任一数都可由4和7组成。 重新翻译题目: 对于任一大于 X X X的正整数 Y Y Y满足 Y a n b m Y a \times nb \times m …...
Nginx简介,Nginx搭载负载均衡以及Nginx部署前端项目
目录 一. Nginx简介 Nginx的优点 二. Nginx搭载负载均衡 2.1 Nginx安装 2.1.1 安装依赖 2.1.2 解压nginx安装包 2.1.3 安装nginx 2.1.4 启动nginx服务 2.2 tomcat负载均衡 2.3 Nginx配置 三. Nginx前端部署 一. Nginx简介 NGINX(读作:engi…...
QT5.15.2搭建Android编译环境及使用模拟器调试(全)
一、安装QT5.15.2 地址:下载 我电脑的windows的,所以选windows 由于官方安装过程非常非常慢,一定要跟着步骤来安装,不然慢到怀疑人生 1)打开"命令提示符"(开始 -> Windows 系统 -> 命令…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
