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

面试热题(x的平方根)

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

       这道题虽然是简单题,可它表现的也不是那么简单,刚看到题的时候,我也想的是用内置函数,可是正当我写的时候,看到了题目的要求(可我还是用)

return (int)Math.pow(x,0.5);

 我又拿了其他方式写了几次,现在给大家分享一下我的做题思路

第一种方式(找区间):

我们可以假设为该区间是由红绿颜色组成的,红色代表的是小于等于目标值,绿色代表大于目标值,这样:

 通过不断的移动,指针终会从红色变为绿色,我们求的目标值就是红色区域的最后一个元素

 //利用二分查找进行求解public int mySqrt(int x) {if(x==0||x==1){return x;}int r=find(x,0,x);return r-1;}public boolean isGree(int val,int x){return (long)val*val>x;}public int find(int x,int left,int right){if(left>right){return 0;}//找到最右侧的第一个红色while(left<right){int mid=left+(right-left)/2;if(isGree(mid,x)){right=mid;}else{left=mid+1;}}return left;}

 方法二(普通的二分搜索)

    public int mySqrt(int x) {if(x==0||x==1){return x;}int left=0;int  right=x;while(left<=right){int mid=left+(right-left)/2;if(mid==x/mid){return mid;}else if(mid<x/mid){left=mid+1;}else{right=mid-1;}}return right;}

方法三(最右侧的二分搜索):

       这种方法我觉的你学会了你才是对二分搜索有了一定的理解,它的取值范围还是它的边界初始值,因为这种靠左侧靠右侧的方法训话条件都是left<right,而不是left等于right,因为题目中给定的参数根号x是可以取到的,所以我们为了凑写个条件写成right=x+1,这样就可以套我们的模板了,具体模板看一起学算法(二分搜索篇)

 public int mySqrt(int x) {if(x==0||x==1){return x;}int left=0;int  right=x+1;while(left<right){int mid=left+(right-left)/2;if(mid<=x/mid){left=mid+1;}else{right=mid;}}return left-1;}

模板就套好了,当我提交的时候,错了!!!

 最后几个居然过不去,遇到这种情况过不去,千万别回头检查代码的问题,过了90%多的代码一般不会出现什么大的问题,我建议的方法是直接打表

      if(x==2147483647){return 46340;}

然后过了,这种直接打表的方式还是很好用的,效率也嘎嘎高!!!

相关文章:

面试热题(x的平方根)

给你一个非负整数 x &#xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数&#xff0c;结果只保留 整数部分 &#xff0c;小数部分将被 舍去 。 注意&#xff1a;不允许使用任何内置指数函数和算符&#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 这道题虽然是简单题…...

食品溯源合约 -- 智能合约实例

前提 Roles: 实现对用户地址的角色权限管控,添加、删除角色。 Producer: 生产商角色管控。 ... FoodInfoItem: 食品信息管控。生产商、中间商、超市添加食品信息。 Trace:食品溯源合约,主要负责对以上几个合约的统筹协作。 Roles // SPDX-License-Identifier: MIT pragm…...

SAP系统中二代增强提供了4中增强函数的查找方法

1 Introduction The second enhancement is used widely by sap .We can set break-point in the function . The function is in the SMOD FG. 2 Detail SAP系统中二代增强提供了4中增强函数的查找方法&#xff1a; MODX_ALL_ACTIVE_MENUENTRIES (菜单增强) MODX_FUNCTION…...

RabbitMQ-SpringBoot2

1.依赖引用 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-amqp</artifactId> </dependency> 2.配置文件 spring: rabbitmq: host: 192.168.2.17 port: 5672 usernam…...

MyBatis核心 - SqlSession如何通过Mapper接口生成Mapper对象

书接上文 MyBatis – 执行流程 我们通过SqlSession获取到了UserMapper对象&#xff0c;代码如下&#xff1a; // 获取SqlSession对象 SqlSession sqlSession sqlSessionFactory.openSession();// 执行查询操作 try {// 获取映射器接口UserMapper userMapper sqlSession.get…...

【Git】标签管理与Git Flow模型

目录 一、操作标签 二、推送标签 三、删除标签 四、Git Flow模型分支设计 一、操作标签 git tag # 查看有哪些标签 git tag [name] # 给最近一次commit打标签 git tag [name] [commitID] #给指定的commit打标签 git tag -a [name] -m desc # 打标签并添加描述 二、推送标…...

日志分析和流量分析

目录 [陇剑杯 2021]日志分析&#xff08;问1&#xff09; [陇剑杯 2021]日志分析&#xff08;问2&#xff09; [陇剑杯 2021]日志分析&#xff08;问3&#xff09; [陇剑杯 2021]简单日志分析&#xff08;问1&#xff09; [陇剑杯 2021]简单日志分析&#xff08;问3&#…...

typescript基础之关键字type

TypeScript的type是一个关键字&#xff0c;用来定义一个类型别名https://www.typescripttutorial.net/typescript-tutorial/typescript-types/。类型别名可以给一个已有的类型起一个新的名字&#xff0c;或者组合多个类型成为一个新的类型。例如&#xff1a; // 给string类型起…...

无人机航测技术有何特点?主要应用在哪些方面?

无人机航测是航空摄影测量的一种&#xff0c;主要面向低空遥感领域&#xff0c;具有成本低、快速高效、适用范围广等特点。目前&#xff0c;无人机航测主要应用于地形测绘、城市数字化建设、工程建设等方面。 无人机航测技术的特点 1、作业成本低 传统的人工测量技术主要利用…...

24届近5年杭州电子科技大学自动化考研院校分析

今天给大家带来的是杭州电子科技大学控制考研分析 满满干货&#xff5e;还不快快点赞收藏 一、杭州电子科技大学 学校简介 杭州电子科技大学&#xff08;Hangzhou Dianzi University&#xff09;&#xff0c;简称“杭电”&#xff0c;位于杭州市&#xff0c;是浙江省人民政…...

调整vscode

调整vscode 连wifi linux连接wifi...

Spring xml 方式整合mybatis 第三方框架

Spring整合MyBatis MyBatis提供了mybatis-spring.jar专门用于两大框架的整合。 ①&#xff1a;第一步&#xff1a; 导入MyBatis整合Spring的相关坐标&#xff1b; <!-- https://mvnrepository.com/artifact/org.mybatis/mybatis-spring --> <dependency><groupI…...

RabbitMQ(二) - RabbitMQ与消息发布确认与返回、消费确认

RabbitMQ消息确认 SpringBoot与RabbitMQ整合后&#xff0c;对RabbitClient的“确认”进行了封装、使用方式与RabbitMQ官网不一致&#xff1b; 消息发布确认 生产者给交换机发送消息后、若是不管了&#xff0c;则会出现消息丢失&#xff1b; 解决方案1&#xff1a; 交换机接受…...

操作指南 | 如何使用Chainlink喂价功能获取价格数据

Chainlink的去中心化预言机网络中的智能合约包含由运行商为其他智能合约&#xff08;DApps&#xff09;使用或截取所持续更新的实施价格数据。其中有两个主要架构&#xff1a;喂价和基础要求模型。此教程将会展现如何在Moonbeam、Moonriver或是Moonbase Alpha测试网上使用喂价功…...

Pandaer的iPhone手机壳

哇塞&#xff0c;Pandaer的设计太棒了&#xff01;手机壳的花样多到让我眼花缭乱&#xff0c;好多系列设计都很有意思&#xff0c;让人有集齐的冲动。我最近入手了几个iPhone的手机壳&#xff0c;它有亮色和透明的款式&#xff0c;亮色的壳内部也是亮的&#xff0c;因为手机壳全…...

将自己的网站免费发布到互联网上【无需公网IP】

作者简介&#xff1a; 辭七七&#xff0c;目前大一&#xff0c;正在学习C/C&#xff0c;Java&#xff0c;Python等 作者主页&#xff1a; 七七的个人主页 文章收录专栏&#xff1a; 七七的闲谈 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01;&#x1f496;&#x1f…...

浅谈 Python中if __name__ == ‘__main__‘:的工作原理

为了理解if __name__ __main__:的工作原理&#xff0c;我们需要先了解Python中的特殊变量__name__。 每个Python模块都有一个内置的变量__name__。这个变量的值取决于如何执行模块&#xff1a; 如果模块是被直接运行的&#xff08;例如&#xff0c;你使用命令python myscrip…...

【力扣】344. 反转字符串 <首尾指针>

【力扣】344. 反转字符串 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间&#xff0c;你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 示例 1&#xff1a; 输入&#xff1a;s …...

Kubectl 详解

目录 陈述式资源管理方法&#xff1a;项目的生命周期&#xff1a;创建-->发布-->更新-->回滚-->删除声明式管理方法&#xff1a; 陈述式资源管理方法&#xff1a; kubernetes 集群管理集群资源的唯一入口是通过相应的方法调用 apiserver 的接口kubectl 是官方的CL…...

华为OD面试记录

The experience of applying for software test engineer(Dispatcher) 记录保存 招聘岗位: 测试工程师 Base:西安 华为面试流程如下&#xff1a; 流程名内容机试三题,总分400分,最后一道题200分人力资源面试询问私人问题&#xff0c;不谈薪资一面技术面二面技术面主管问项目…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

Python常用模块:time、os、shutil与flask初探

一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...

向量几何的二元性:叉乘模长与内积投影的深层联系

在数学与物理的空间世界中&#xff0c;向量运算构成了理解几何结构的基石。叉乘&#xff08;外积&#xff09;与点积&#xff08;内积&#xff09;作为向量代数的两大支柱&#xff0c;表面上呈现出截然不同的几何意义与代数形式&#xff0c;却在深层次上揭示了向量间相互作用的…...