0069-leetcode算法实现之x的算术平方根-sqrtx-python&golang实现

互联网 2021/10/14 11:14:10

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。 注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。示例 1: 输入:x = 4 输出:2 示例 2: 输入:x = 8 输出:2 解释:…

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

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

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

示例 1:

输入:x = 4
输出:2
示例 2:

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

提示:

0 <= x <= 231 - 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sqrtx

python

# x的算术平方根
class Solution:
    # 二分法
    def sqrtx(self, x: int) -> int:
        if x < 0:
            return -1
        left, right, ans = 0, x, x
        while left <= right:
            mid = left + ((right-left)>>1)
            if mid*mid > x:
                right = mid - 1
            else:
                ans = mid
                left = mid + 1
        return ans
    # 牛顿-拉夫逊迭代
    def sqrtx_newton(self, x: int) -> int:
        if x < 0:
            return -1
        elif x == 0:
            return 0

        C, x0 = float(x), float(x)
        while True:
            xi = 0.5 * (x0 + C/x0)
            if abs(x0-xi) < 1e-7:
                break
            x0 = xi
        return int(x0)


if __name__ == "__main__":
    x = 256
    test = Solution()
    print(test.sqrtx(x))
    print(test.sqrtx_newton(x))

golang

package main

import (
	"fmt"
	"math"
)

func main() {
	var x int = 656
	fmt.Println(sqrtx(x))
	fmt.Println(sqrtxNewton(x))
}

func sqrtx(x int) int {
	if x < 0 {
		return -1
	}
	var left int = 0
	var right int = x
	var ans int = -1
	for left <= right {
		var mid int = left + ((right - left) >> 1)
		if mid*mid > x {
			right = mid - 1
		} else {
			ans = mid
			left = mid + 1
		}
	}
	return ans
}

func sqrtxNewton(x int) int {
	if x < 0 {
		return -1
	} else if x == 0 {
		return 0
	}

	C := float64(x)
	x0 := float64(x)
	for {
		xi := 0.5 * (x0 + C/x0)
		if math.Abs(x0 - xi) < 1e-7 {
			break
		}
		x0 = xi
	}
	return int(x0)
}
随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[0069-leetcode算法实现之x的算术平方根-sqrtx-python&golang实现]http://www.zyiz.net/tech/detail-241266.html

上一篇:Python中作用域

下一篇:Python 实例方法、类方法、静态方法的区别与作用

赞(0)
关注微信小程序
程序员编程王-随时随地学编程

扫描二维码或查找【程序员编程王】

可以随时随地学编程啦!

技术文章导航 更多>
扫一扫关注最新编程教程