leetcode刷题69 x的平方根 Sqrt(x)(简单) Python Java

2024-01-27 00:08

本文主要是介绍leetcode刷题69 x的平方根 Sqrt(x)(简单) Python Java,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目大意:

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。

解法一:使用二分查找法,对中间数进行判断,如果mid^2 <= x 且 (mid+1)^2>x,则说明int(mid)即为所求

class Solution(object):def mySqrt(self, x):""":type x: int:rtype: int"""if x <= 1:return xbig = xsmall = 0while small <= big:mid = int((big+small)/2)if (mid**2) > x and x>=(mid-1)**2:return int(mid)-1elif x > mid**2:small = mid + 1elif x < (mid-1)**2:big = mid-1else:return int(mid)

在Python3中  *  代表乘法,** 代表乘方

解法二:

算法:牛顿迭代法(详细解释可自行查询)。
在这简单介绍一下:
求一个值 a 的平方根,那么首先令 x = a,然后不断令 x = (x + a/x)/2,这样迭代几次之后得到的数值就趋近于准确值了。

class Solution:def mySqrt(self, x):""":type x: int:rtype: int"""if x < 2:return xn = xwhile n > x // n:n = (n + x // n) // 2return n

 

以下是Java版本:

题意:算一个数的平方根。

注意点就是:取中值相乘,有可能会超过整数的最大范围,所以比较的时候就会出错。所以在定义的时候全部定义为long

public class Sqrt {public int mySqrt(int x) {  if (x == 0)  return 0;  long low = 1;  long high = x;  long tmp;long mid = 1;  while (low <= high)//二分查找  {  mid = (low + high) / 2;  tmp = mid * mid;  if (tmp == x)  return (int)mid;  else if (tmp > x)  high = mid - 1;  else if (tmp < x)low = mid + 1; }  return (int)((mid*mid)>x?mid-1:mid);  
}  

这道题很巧妙的运用了二分查找法的特性,有序,查找pos(在这道题中pos=value),找到返回pos,找不到返回邻近值。

因为是求数xx>=0) 的平方根, 因此,结果一定是小于等于x且大于等于0,所以用二分查找法肯定能搜到结果。

以每一次的mid的平方来与target既数x相比:

如果mid*mid == x,返回mid

如果mid*mid < x,那么说明mid过小,应让low = mid+1,在右边继续查找

如果mid*mid > x,那么说明mid过大,应让high = mid-1,在左边继续查找

x无法开整数根号(在上述查找中没有找到),那么我们仍然可以利用之前对二分查找法总结的技巧,当target值不在数组中,low指向大于target的那个值,high指向小于target的那个值,由于我们需要向下取整的结果,所以我们返回high指向的值(这里high指向的值和high的值是同一个值),这个值就是所求得最接近起开根号结果的整数值。

因为leetcodetest case x=2147395599,在算mid*mid的时候造成溢出,所以mid不能使用int型来接,要使用long型防止溢出(JavaInteger型的范围:-2147483648 2147483648

 1 public int sqrt(int x) {2         int low = 0;3         int high = x;4         while(low<=high){5             long mid = (long)(low + high)/2;6             if(mid*mid < x)7                 low = (int)mid + 1;8             else if(mid*mid > x)9                 high = (int)mid - 1;
10             else
11                 return (int)mid;
12         }
13         return high;
14 }

 

这篇关于leetcode刷题69 x的平方根 Sqrt(x)(简单) Python Java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/648470

相关文章

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

浅析Spring如何控制Bean的加载顺序

《浅析Spring如何控制Bean的加载顺序》在大多数情况下,我们不需要手动控制Bean的加载顺序,因为Spring的IoC容器足够智能,但在某些特殊场景下,这种隐式的依赖关系可能不存在,下面我们就来... 目录核心原则:依赖驱动加载手动控制 Bean 加载顺序的方法方法 1:使用@DependsOn(最直

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

Python办公自动化实战之打造智能邮件发送工具

《Python办公自动化实战之打造智能邮件发送工具》在数字化办公场景中,邮件自动化是提升工作效率的关键技能,本文将演示如何使用Python的smtplib和email库构建一个支持图文混排,多附件,多... 目录前言一、基础配置:搭建邮件发送框架1.1 邮箱服务准备1.2 核心库导入1.3 基础发送函数二、

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab