首页 > 编程语言 >【算法】求 x 的平方根

【算法】求 x 的平方根

时间:2024-03-15 15:11:06浏览次数:23  
标签:right int res 整数 算法 平方根 left

leetcode 链接

题目描述

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

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

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

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

提示:

  • 0 <= x <= 231 - 1

解法一:二分查找

x=0 时,返回 0;

left > right 时,循环结束,此时,left ** 2 > xright ** 2 <= x,所以返回 right

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right= 1, x
        while left <= right:
            mid = left + (right - left) // 2
            # 避免乘法溢出,改用除法
            if mid <= x / mid:
                left = mid + 1
            else:
                right = mid - 1
        return right

解法二:牛顿迭代

牛顿迭代法能快速求解函数零点的近似值。

假设 X 是待求平方根的整数,X的平方根就是函数

\[f(x) = x^2-X \]

的零点。

而我们可以用牛顿迭代法快速逼近函数零点。

image-20240315145845240

因为 \(f'(x)=2x\),所以

\[\begin{align} x_{k+1} &= x_k - \frac{x_k^2-X}{2x_k} \\ &= \frac{1}{2}(x_k+\frac{X}{x_k}) \end{align} \]

class Solution:
    def mySqrt(self, x: int) -> int:
        res = x
        while res * res > x:
            res = (res + x // res) // 2
        return (int)res

标签:right,int,res,整数,算法,平方根,left
From: https://www.cnblogs.com/hzyuan/p/18075437

相关文章

  • 用A*算法设计搜索策略,补全关于下列走迷宫问题的程序
    补全下列关于走迷宫的程序:classNode():#TODO:完成结点类的定义,结点中要包含状态、父结点、算符等必要成员。根据算法需求,还可能包含该结点的路径代价、启发函数值、估计代价等信息def__init__(self,state,parent,action,stepCost,hCost):self.st......
  • 代码随想录算法训练营第四十七天| ● 198.打家劫舍 ● 213.打家劫舍II ● 337.打家
    打家劫舍 题目链接:198.打家劫舍-力扣(LeetCode)思路:每一家的最大收益来源只有两个,一个是这家不偷,那么最大收益等于从上一家出来的最大收益,另一个是偷这一个家,因此最大收益等于从上上一家出来的最大收益加这一家的收益。classSolution{public:introb(vector<int>&nu......
  • 代码随想录算法训练营第四十七天 | 337.打家劫舍III,213.打家劫舍II ,198.打家劫舍
     198.打家劫舍 已解答中等 相关标签相关企业 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一......
  • Light Random Sprays Retinex 传统的图像增强算法LRSR
    文章目录前言1、LightRandomSpraysRetinex概况2、LightRandomSpraysRetinex具体实现2.1、噪声去除2.2、亮度调整2.3、插值技术3、LightRandomSpraysRetinex源码4、LightRandomSpraysRetinex效果及结论前言  LightRandomSpraysRetinex,即“光随......
  • 基于python+django的协同过滤算法的小说推荐系统
    摘 要随着世界经济信息化、全球网络化的到来推动信息线上管理的飞速发展,为小说推荐的管理起到关件作用。若想达到安全,快捷的目的,就需要拥有信息化的组织和管理模式,建立一套合理、畅通、高效的小说推荐系统,通过此网站爬虫技术获取数据。当前的银行用户行为管理存在工作效率......
  • 聚类算法-K-means
    主要在K-means的理解1介绍K-means算法,以及具体的过程K-means算法是常用的聚类算法之一,属于无监督学习,主要用来将标签未知的数据划分成较少的类/簇,类内的样本差异要小,类间的样本差异要大,这可以帮助我们探索数据结构和分布。K-means的具体实现过程:(四步)初始化模型参数:聚类的簇......
  • 人工智能时代,Java从业者必学科目:数据机构和算法,以及AI算法和技能
    【晋升攻略】Java开发者的AI时代高薪加速器在AI时代,Java从业者必学的科目包括数据结构与算法、AI算法和相关技能,这是因为这些知识和技能是构建和发展人工智能应用的基础。具体分析如下:1.数据结构与算法:数据结构和算法是计算机科学的核心,对于编写高效、可维护的代码至关重......
  • 代码随想录算法训练营第七天|LeetCode 344.反转字符串、541.反转字符串II、卡码网54.替
    344.反转字符串题目描述:​编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用O(1)的额外空间解决这一问题。示例一:输入:s=["h","e","l","l","o"]输出:["o","l","l......
  • 代码随想录算法训练营第十天| 232. 用栈实现队列 225. 用队列实现栈
    232.用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;publicMyQueue(){stackIn=newStack<>();stackOut=new......
  • 贪心算法(算法竞赛、蓝桥杯)--均分纸牌
    1、B站视频链接:A30贪心算法P1031[NOIP2002提高组]均分纸牌_哔哩哔哩_bilibili题目链接:[NOIP2002提高组]均分纸牌-洛谷#include<bits/stdc++.h>usingnamespacestd;intn,a[101],av,cnt;intmain(){ scanf("%d",&n); for(inti=1;i<=n;i++){ scanf("%d&quo......