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

【Java】再一次踩了整数溢出的坑

【Java】再一次踩了整数溢出的坑

  • 一、起因
    • 原题
      • 示例 1
      • 示例 2
      • 提示
    • 我的代码
    • 提交结果
  • 二、思考
    • 修改后的代码如下
  • 三、知识点
    • 1. `int m = l + ((r - l) / 2)`
      • 解释
    • 2. `if (m < x / m)`
      • 解释
  • 四、结尾

一、起因

我在做【力扣】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

我的代码

class Solution {public int mySqrt(int x) {//处理特殊值 0 和 1if (x == 0) {return 0;}if (x == 1) {return 1;}//二分法查找int l = 1, r = x / 2;while (l <= r) {int m = l + ((r - l) / 2);if (m * m == x) {return m;} else if (m * m < x) {l = m + 1;} else {r = m - 1;}}if (r <= l) {return r;} else {return l;}}
}

提交结果

输入:2147395599
输出:1073697799
预期结果:46339

二、思考

我反复检查代码的逻辑,都没发现问题出现在哪里,直到我看见 别人的题解。
对比代码之后我恍然大悟,明白自己又踩了整数溢出的坑。

修改后的代码如下

class Solution {public int mySqrt(int x) {//处理特殊值 0 和 1if (x == 0) {return 0;}if (x == 1) {return 1;}//二分法查找int l = 1, r = x / 2;while (l <= r) {int m = l + ((r - l) / 2);if (m == x / m) {return m;} else if (m < x / m) {l = m + 1;} else {r = m - 1;}}return r;}
}

三、知识点

1. int m = l + ((r - l) / 2)

int m = l + ((r - l) / 2) 而不是直接写 int m = (l + r) / 2 是为了防止整数溢出

解释

  • 假设我们写的是 int m = (l + r) / 2
    lr 都是非常大的正整数时(接近 Integer.MAX_VALUE,即 2147483647),l + r 可能会超过 int 类型的最大表示范围 (2^31 - 1),这会导致溢出,结果会变成负数,从而导致程序的行为不符合预期。
    如: l = 2000000000r = 2000000000,那么 l + r = 4000000000,这是超过 int 的最大值 2147483647 的,会产生溢出。

  • 假设我们写的是 int m = (l + r) / 2
    r > l 时,r - l 不会溢出,它是一个较小的数,(r - l) / 2 也不会产生太大的值,最终加上 l,依然保持在 int 范围内。

2. if (m < x / m)

m < x / m 而不写 m * m < x 也是为了防止整数溢出

解释

原理同上。
m * m > 2147483647 时会发生整数溢出,结果会变成负数,导致程序的行为不符合预期。

四、结尾

当然,也可以将 m * m < x 改成 (long) m * m < x,这样就不用担心整数溢出了,因为 long 类型的最大值比 int 类型的最大值大得多。

相关文章:

【Java】再一次踩了整数溢出的坑

【Java】再一次踩了整数溢出的坑 一、起因原题示例 1示例 2提示 我的代码提交结果 二、思考修改后的代码如下 三、知识点1. int m l ((r - l) / 2)解释 2. if (m < x / m)解释 四、结尾 一、起因 我在做【力扣】69.x 的平方根 一题的时候&#xff0c;明明觉得逻辑没问题&…...

Windows开发工具使用技巧大揭秘:让编码效率翻倍的秘籍!

【ACM出版|厦大主办|EI稳定检索】第五届计算机科学与管理科技国际学术会议&#xff08;ICCSMT 2024&#xff09;_艾思科蓝_学术一站式服务平台 更多学术会议请看&#xff1a;学术会议-学术交流征稿-学术会议在线-艾思科蓝 目录 引言 1. 快捷键大全&#xff1a;加速你的编码…...

CSS外边距

元素的外边距&#xff08;margin&#xff09;是围绕在元素边框以外&#xff08;不包括边框&#xff09;的空白区域&#xff0c;这片区域不受 background 属性的影响&#xff0c;始终是透明的。 为元素设置外边距 默认情况下如果不设置外边距属性&#xff0c;HTML 元素就是不会…...

C++ set,multiset与map,multimap的基本使用

1. 序列式容器和关联式容器 string、vector、list、deque、array、forward_list等STL容器统称为序列式容器&#xff0c;因为逻辑结构为线性序列的数据结构&#xff0c;两个位置存储的值之间一般没有紧密的关联关系&#xff0c;比如交换一下&#xff0c;他依旧是序列式容器。顺…...

评估潜力无限:解读自闭症患者的工作能力评估

在星贝育园这片充满爱与希望的土地上&#xff0c;我们不仅见证了无数自闭症儿童在康复训练中的点滴进步&#xff0c;更深刻理解了他们内在潜力的无限可能。自闭症&#xff0c;这一复杂的神经发育障碍&#xff0c;常常让外界对其患者的工作能力产生误解和偏见。然而&#xff0c;…...

js 实现视频封面截图

今天给大家分享一下&#xff0c;如何实现视频封面截取功能&#xff0c;这里主要用到了 HTML5 的 canvas 相关的 api 和 js 相关的一些知识&#xff0c;话不多说&#xff0c;直接上代码&#xff1a; <template><div><div class"margin-tb-sm"><…...

Hadoop FileSystem Shell 常用操作命令

提示&#xff1a;本文章只总结一下常用的哈&#xff0c;详细的命令大家可以移步官方的文档&#xff08;链接贴在下面了哈&#x1f923;&#xff09;— HDFS官方命令手册链接。 目录 1. cat 命令&#xff1a;查看 HDFS 文件内容2. put 命令&#xff1a;将本地文件上传到 HDFS3.…...

uniapp EChars图表

1. uniapp EChars图表 &#xff08;1&#xff09;Apache ECharts 一个基于 JavaScript 的开源可视化图表库   https://echarts.apache.org/examples/zh/index.html &#xff08;1&#xff09;官网图例 &#xff08;2&#xff09;个人实现图例 1.1. 下载echart 1.1.1. 下…...

最新版ingress-nginx-controller安装 使用host主机模式

最新版ingress-nginx-controller安装 使用host主机模式 文章目录 最新版ingress-nginx-controller安装 使用host主机模式单节点安装方式多节点高可用安装方式 官方参考链接&#xff1a; https://github.com/kubernetes/ingress-nginx/ https://kubernetes.github.io/ingress-ng…...

实习问题(配置文件获取参数)

Java中用SpringBoot框架&#xff0c;当我们要获取配置文件yml里的参数时&#xff0c;用Value注解获取 如果配置文件中没有srvSealUploadPath这个参数的话&#xff0c;可以用Value("${srvSealUploadPath:data/idoc/temp}")&#xff0c;这个的意思是&#xff0c;如果配…...

C#测试调用Ghostscript.NET浏览PDF文件

Ghostscript.NET是针对Ghostscript的C#封装库&#xff0c;支持解析PostScript语言、操作PDF文件等。使用Ghostscript.NET的GhostscriptViewer 模块可以以图片形式查看PDF文档。本文学习并测试调用Ghostscript.NET模块打开及浏览PDF文件的基本用法。   Ghostscript.NET目前主要…...

MySQL本地安装步骤

下载MySQL ZIP压缩包 访问MySQL官网&#xff08;https://www.mysql.com/&#xff09;或下载页面&#xff08;https://dev.mysql.com/downloads/mysql/&#xff09;。 在下载页面选择“MySQL Community Server”作为下载目标。 根据你的操作系统&#xff08;Windows&#xff09;…...

redisson使用笔记

文章目录 spring集成redisson maven配置yml配置使用redisTemplate和redisson的区别 其他项目中看到redisson&#xff0c;看样子像是redis相关类库&#xff0c;实际也确实是。 还是老规矩&#xff0c;见到的要了解&#xff0c;需要的必须掌握&#xff0c;了解一下吧。 spring集成…...

设计模式之享元(Flyweight)模式

前言 面向对象很好地解决了 “抽象” 的问题&#xff0c;但是不可避免的要付出一定的代价。对于通常情况来讲&#xff0c;面向对象的成本大都可以忽略不计。但是某些情况&#xff0c;面向对象所带来的成本必须谨慎处理 具体需要自己根据需求去评估 定义 “对象性能” 模式。运用…...

桥接(桥梁)模式

简介 桥接模式&#xff08;Bridge Pattern&#xff09;又叫作桥梁模式、接口&#xff08;Interface&#xff09;模式或柄体&#xff08;Handle and Body&#xff09;模式&#xff0c;指将抽象部分与具体实现部分分离&#xff0c;使它们都可以独立地变化&#xff0c;属于结构型…...

语言模型发展史

四个阶段 第一阶段&#xff1a;基于规则和统计的语言模型 由人工设计特征并使用统计方法对固定长度的文本窗口序列进行建模分析&#xff0c;这种建模方式也被称为N-gram语言模型。 优点&#xff1a; 1&#xff09;采用极大似然估计, 参数易训练 2&#xff09;完全包含了前n-…...

【Linux】模拟实现一个shell

接受每一个人的批评&#xff0c;可是保留你自己的判断。 ——莎士比亚 一段时间的没有更新是由于最近开学期间比较的忙&#xff0c;同时也是由于刚开学的几门课才学习的时候有点迷糊&#xff0c;需要在学校课堂上花的时间更多了&#xff0c;所以才没有更新的&#xff0c;求放过…...

云原生数据库 PolarDB

简介&#xff1a;云原生数据库 PolarDB 是阿里云自研产品&#xff0c;在存储计算分离架构下&#xff0c;利用了软硬件结合的优势&#xff0c;为用户提供秒级弹性、高性能、海量存储、安全可靠的数据库服务。100%兼容MySQL和PostgreSQL生态&#xff0c;支持分布式扩展&#xff0…...

MobaXterm基本使用 -- 服务器状态、批量操作、显示/切换中文字体、修复zsh按键失灵

监控服务器资源 参考网址&#xff1a;https://www.cnblogs.com/144823836yj/p/12126314.html 显示效果 MobaXterm提供有这项功能&#xff0c;在会话窗口底部&#xff0c;显示服务器资源使用情况 如内存、CPU、网速、磁盘使用等&#xff1a; &#xff08;完整窗口&#xff0…...

elastic Search 初步之向量检索的数据写入及检索查询

### Elasticsearch 向量检索实现方法方案 Elasticsearch 从 7.3 版本开始引入了向量检索功能,支持通过向量字段进行相似度搜索。以下是实现向量检索的步骤和方案,包括 Python 和 Java 版本的代码示例。 #### 1. 最低实现向量检索的 ES 版本 - **最低版本**: Elasticsearch …...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

yaml读取写入常见错误 (‘cannot represent an object‘, 117)

错误一&#xff1a;yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因&#xff0c;后面把yaml.safe_dump直接替换成yaml.dump&#xff0c;确实能保存&#xff0c;但出现乱码&#xff1a; 放弃yaml.dump&#xff0c;又切…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...

python基础语法Ⅰ

python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器&#xff0c;来进行一些算术…...

Linux入门(十五)安装java安装tomcat安装dotnet安装mysql

安装java yum install java-17-openjdk-devel查找安装地址 update-alternatives --config java设置环境变量 vi /etc/profile #在文档后面追加 JAVA_HOME"通过查找安装地址命令显示的路径" #注意一定要加$PATH不然路径就只剩下新加的路径了&#xff0c;系统很多命…...

OpenGL-什么是软OpenGL/软渲染/软光栅?

‌软OpenGL&#xff08;Software OpenGL&#xff09;‌或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式&#xff08;包括几何处理、光栅化、着色等&#xff09;&#xff0c;不依赖GPU硬件加速。这种模式通常性能较低&#xff0c;但兼容性极强&#xff0c;常用于不支持硬件加速…...

性能优化中,多面体模型基本原理

1&#xff09;多面体编译技术是一种基于多面体模型的程序分析和优化技术&#xff0c;它将程序 中的语句实例、访问关系、依赖关系和调度等信息映射到多维空间中的几何对 象&#xff0c;通过对这些几何对象进行几何操作和线性代数计算来进行程序的分析和优 化。 其中&#xff0…...

Shell 解释器​​ bash 和 dash 区别

bash 和 dash 都是 Unix/Linux 系统中的 ​​Shell 解释器​​&#xff0c;但它们在功能、语法和性能上有显著区别。以下是它们的详细对比&#xff1a; ​​1. 基本区别​​ ​​特性​​​​bash (Bourne-Again SHell)​​​​dash (Debian Almquist SHell)​​​​来源​​G…...

Python 解释器安装全攻略(适用于 Linux / Windows / macOS)

目录 一、Windows安装Python解释器1.1 下载并安装Python解释1.2 测试安装是否成功1.3 设置pip的国内镜像------永久配置 二、macOS安装Python解释器三、Linux下安装Python解释器3.1 Rocky8.10/Rocky9.5安装Python解释器3.2 Ubuntu2204/Ubuntu2404安装Python解释器3.3 设置pip的…...