专题三_二分_x 的平方根

一:题目

解释:返回x的算数平方根,如果是小数,则舍去小数部分,返回整数即可!

二:算法

①:暴力

从1开始求平方,最后要么直接找到一个值的平方为x,要么发现x在两个相邻的数的平方之间

暴力的时间复杂度为O(N)

但是我们从暴力得知,最后返回的一定是left,因为双指针相遇返回left和right都可以,但是如果发现x是两个相邻的数的平方之间,则返回left,因为题目要求向下取整

②:二分

做过了上道题目,此题简直如鱼得水!

我们将数组划分为两个部分,左部分值的平方<=x,右部分值的平方>x,本质是因为数组有可能没有直接平方等于x的值,所以左部分是<=

其次我们的区间的范围直接从1~x开始即可,因为只要一个数是正整数,则其一定小于其的平方!

所以:

mid*mid <=x 则left=mid  //落入左部分

mid*mid >x 则right=mid-1 //落入右部分

很显然,我们的求中点的式子必须为:mid = left + (right - left + 1) / 2!

因为,我们说过mid不能落在原地踏步的指针上,此题left=mid,所以不能落在left上,所以我们选择该式子,当只有两个元素的时候,mid会落在right指针上

其次循环的条件必定是left<right,避免双指针相遇再次进入循环,导致原地踏步死循环!

三:代码

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;//long long 防溢出if (mid * mid <= x) left = mid;else right = mid - 1;}return left;}
};

解释:

1:循环条件,left<right

2:求中点式子,mid = left + (right - left + 1) / 2; 

3:返回的是left

4:x可能为0~1之间,所以一开始特判即可

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/web/93220.shtml
繁体地址,请注明出处:http://hk.pswp.cn/web/93220.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python 操作 Redis 的客户端库 redis-py

Python 操作 Redis 的客户端库 redis-py1. Installation2. Connect and test3. Connection Pools4. Redis Commands4.1. set(name, value, exNone, pxNone, nxFalse, xxFalse, keepttlFalse, getFalse, exatNone, pxatNone)4.1.1. setnx(name, value)4.1.2. setex(name, time, …

社区物业HCommunity本地部署手册

HC小区管理系统安装手动版 更多文章参考&#xff1a; http://www.homecommunity.cn/pages/hc/hcH5_cn.html 1.0 说明 很多开发不太喜欢用梓豪安装&#xff0c;希望通过手工自己安装&#xff0c;这个就需要开发人员 有一定的安装软件能力&#xff0c;比如能够自行安装mysql能…

单例模式-使用局部变量懒汉不用加锁

在 C11 及之后&#xff0c;“局部静态变量懒汉”&#xff08;Meyers’ Singleton&#xff09;不需要自己加锁&#xff0c;标准已经帮你做好了线程安全。 Singleton& getInstance() {static Singleton inst; // ← 这一句并发时只会初始化一次return inst; }首次调用时&am…

51单片机-GPIO介绍

本章概述思维导图&#xff1a;51单片机引脚介绍STC89系列51单片机引脚介绍STC89系列51单片机的引脚是单片机与外部电路连接的接口&#xff0c;用于实现电源供电、时钟信号输入、控制信号输出以及数据输入输出等功能。PDIP封装引脚图&#xff1a;1. 电源引脚&#xff1a;VCC&…

CERT/CC警告:新型HTTP/2漏洞“MadeYouReset“恐致全球服务器遭DDoS攻击瘫痪

2025年8月15日CERT/CC&#xff08;计算机应急响应协调中心&#xff09;近日发布漏洞公告&#xff0c;警告多个HTTP/2实现中新发现的缺陷可能被威胁行为者用于发起高效拒绝服务&#xff08;DoS&#xff09;或分布式拒绝服务&#xff08;DDoS&#xff09;攻击。该漏洞被非正式命名…

[Chat-LangChain] 会话图(LangGraph) | 大语言模型(LLM)

第二章&#xff1a;会话图&#xff08;LangGraph&#xff09; 在第一章中&#xff0c;我们学习了前端用户界面——这是聊天机器人的"面孔"&#xff0c;我们在这里输入问题并查看答案。 我们看到了消息如何从聊天窗口传递到聊天机器人的"大脑"。现在&…

Flask错误处理与会话技术详解

flask入门day03 错误处理 1.abort函数&#xff1a;放弃请求并返回错误代码 详细状态码 from flask import Flask,abort,render_template ​ app Flask(__name__) ​ app.route(/) def index():return 我是首页 ​ app.route(/error) def error():abort(404)return 没有找到…

java程序打包成exe,再打成安装包,没有jdk环境下可运行

一、前提条件准备&#xff1a;1、要被打包的程序文件&#xff1a;rest_assistant-1.0-SNAPSHOT.jarapplication.yml2、图标文件tubiao123.ico3、jre4、打包成exe的软件 config.exe4j5、打成安装包的软件 Inno Setup Compiler二、config.exe4j 的 exe打包配置步骤 按照以下图进行…

区块链技术原理(11)-以太坊交易

文章目录什么是交易&#xff1f;交易类型交易生命周期关键概念&#xff1a;Gas 与交易费用交易状态与失败原因总结什么是交易&#xff1f; “交易&#xff08;Transaction&#xff09;” 是从一个账户向另一个账户发送的经过数字签名的指令 。例如&#xff0c;如果 Bob 发送 A…

小兔鲜儿-小程序uni-app(二)

小兔鲜儿-小程序uni-app7.小兔鲜儿 - 用户模块会员中心页(我的)静态结构参考代码会员设置页分包预下载静态结构退出登录会员信息页静态结构获取会员信息渲染会员信息更新会员头像更新表单信息8.小兔鲜儿 - 地址模块准备工作静态结构地址管理页地址表单页动态设置标题新建地址页…

BLE 广播信道与数据信道:冲突避免、信道映射与自适应跳频实现

低功耗蓝牙(BLE)技术凭借低功耗、短距离、低成本的特性,已广泛应用于智能家居、可穿戴设备、工业物联网等领域。在 BLE 协议中,信道管理是保障通信可靠性的核心机制,其中广播信道与数据信道的设计、冲突避免策略、跳频技术更是面试中的高频考点。本文将从基础原理到实战真…

nodejs03-常用模块

nodejs 常用的核心模块 Node.js 是一个基于 Chrome V8 引擎的 JavaScript 运行环境&#xff0c; 它允许 JavaScript 运行在服务器端。Node.js 拥有丰富的标准库&#xff0c;也就是核心模块&#xff0c; 这些模块提供了各种功能&#xff0c; 使得开发服务器端应用程序变得简单高…

多路混音声音播放芯片型号推荐

以下是唯创知音旗下主流的多路声音播放芯片深度解析&#xff0c;结合精准参数、丰富场景及技术特性&#xff0c;满足智能设备多样化音频需求&#xff1a;一、WTV380/890 系列&#xff1a;高集成多模态交互芯片核心参数通道能力&#xff1a;支持8 路独立语音输出&#xff0c;可同…

【C++】自研基 2 Cooley–Tukey

“自研基 2 Cooley–Tukey&#xff1a;倒位序 逐级蝶形&#xff0c;入口 fft(int N, complex f[])”拆成三件事它在讲什么 “基 2 Cooley–Tukey” 指的是最常见的 FFT 算法&#xff1a;长度 N 必须是 2 的整数次幂&#xff0c;把离散傅里叶变换分解成一层一层的“2 点蝶形”运…

小白挑战一周上架元服务——ArkUI04

文章目录前言一、ArkUI是何方神圣&#xff1f;二、声明式UI三、组件1.基础组件2.布局容器组件3.导航组件4.自定义组件5.组件生命周期四、状态管理1.State装饰器: 状态变量2.Prop装饰器&#xff1a;父子单向同步3.Link装饰器&#xff1a;父子双向同步4.Provide/Consume装饰器&am…

剧本杀小程序系统开发:构建剧本杀社交新生态

在社交需求日益多样化的今天&#xff0c;剧本杀凭借其独特的社交属性&#xff0c;成为了人们热衷的社交娱乐方式之一。而剧本杀小程序系统开发&#xff0c;则进一步拓展了剧本杀的社交边界&#xff0c;构建起一个全新的剧本杀社交新生态&#xff0c;让玩家在推理与角色扮演中&a…

AI提高投放效率的核心策略

内容概要人工智能技术正深刻改变着广告投放领域&#xff0c;其核心价值在于显著提升投放效率。通过融合智能算法优化、实时数据分析与自动化投放流程&#xff0c;AI系统能够以前所未有的速度和精度处理海量信息&#xff0c;驱动更精准的营销决策。这不仅大幅缩短了传统人工操作…

OpenBMC 中命令模式的深度解析:从原理到实现

引言 在 OpenBMC 的设计中&#xff0c;命令模式&#xff08;Command Pattern&#xff09;被广泛应用于各种场景&#xff0c;特别是 IPMI 命令处理、异步操作封装和用户请求管理等。本文将深入分析 OpenBMC 中命令模式的实现原理、架构设计以及完整的执行流程&#xff0c;并通过…

从0开始跟小甲鱼C语言视频使用linux一步步学习C语言(持续更新)8.15

第十七天 第五十七&#xff0c;五十八&#xff0c;五十九和六十集 第五十六集 删除链表结点 没什么好说的关键部分代码如图 链表的插入操作 依旧没有啥可以说的代码部分大家看视频就能看懂&#xff0c;大家应该是没有什么问题的吧&#xff1f; 第五十七集 共用体形式结构与结构…

云服务器网站无法访问的系统化故障排查指南及多维度解决方案

当云服务器上的网站突然无法访问时&#xff0c;这种突发状况往往让人措手不及。别担心&#xff0c;我们可以通过系统化的排查流程快速定位问题根源。以下是经过实战验证的故障排除指南&#xff0c;帮您分步解决网站访问异常问题。一、基础状态确认 服务器的生命体征就像人体的脉…