模块三:二分——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

相关文章

多模块的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

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl