算法leetcode｜50. Pow(x, n)（rust重拳出击）-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法leetcode｜50. Pow(x, n)（rust重拳出击）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

50. Pow(x, n)：

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xⁿ ）。

样例 1：

输入：
	x = 2.00000, n = 10
	
输出：
	1024.00000

样例 2：

输入：
	x = 2.10000, n = 3
	
输出：
	9.26100

样例 3：

输入：
	x = 2.00000, n = -2
	
输出：
	0.25000

解释：
2^-2 = 1/2² = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
n 是一个整数
-10⁴ <= xⁿ <= 10⁴

分析：

面对这道算法题目，二当家的再次陷入了沉思。
直接想到的就是模拟，x 循环 n - 1 次乘以 x，时间可以抹平一切，但是会非常慢。
还得是快速幂：
1. 如果 n 是偶数，可得：xⁿ = x^{n / 2} * x^{n / 2}。
2. 如果 n 是奇数，可得：xⁿ = x^{(n - 1) / 2} * x^{(n - 1) / 2} * x。
3. 如果 n 是负数，可得：xⁿ = 1 / x^-n。
需要注意的一点是题目的参数n都是int / i32，一般就是32位有符号整数，有个坑，它的取值范围是【-2147483648，2147483647】，所以如果传参是 -2147483648，直接取反就悲剧了，2147483648刚好超出范围，因此取反的时候要选择有更大空间的类型，也就是长整型。

#include <iostream>

int main() {
    int n = INT_MIN;
//    -2147483648
//    -2147483648
//    2147483648
    std::cout << n << std::endl << -n << std::endl << -(long)n;
    return 0;
}

快速幂的使用频率还是很高的，应该要熟练掌握。

题解：

rust：

impl Solution {
    pub fn my_pow(x: f64, n: i32) -> f64 {
        fn quickMul(mut x: f64, mut n: i64) -> f64 {
            let mut ans = 1.0;
            // 在对 N 进行二进制拆分的同时计算答案
            while n > 0 {
                if n & 1 == 1 {
                    // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x;
                }
                // 将贡献不断地平方
                x *= x;
                // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                n >>= 1;
            }
            return ans;
        }

        return if n >= 0 {
            quickMul(x, n as i64)
        } else {
            1.0 / quickMul(x, -(n as i64))
        }
    }
}

go：

func myPow(x float64, n int) float64 {
    quickMul := func(x float64, n int) float64 {
		ans := 1.0
		// 在对 N 进行二进制拆分的同时计算答案
		for n > 0 {
			if n&1 == 1 {
				// 如果 N 二进制表示的最低位为 1，那么需要计入贡献
				ans *= x
			}
			// 将贡献不断地平方
			x *= x
			// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
			n >>= 1
		}
		return ans
	}

	if n >= 0 {
		return quickMul(x, n)
	} else {
		return 1.0 / quickMul(x, -n)
	}
}

c++：

class Solution {
private:
    double quickMul(double x, long long n) {
        double ans = 1.0;
        // 在对 N 进行二进制拆分的同时计算答案
        while (n > 0) {
            if (n & 1 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x;
            }
            // 将贡献不断地平方
            x *= x;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            n >>= 1;
        }
        return ans;
    }
public:
    double myPow(double x, int n) {
        return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -(long)n);
    }
};

python：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quick_mul(x, n):
            ans = 1.0
            # 在对 N 进行二进制拆分的同时计算答案
            while n > 0:
                if n & 1 == 1:
                    # 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x
                # 将贡献不断地平方
                x *= x
                # 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                n >>= 1
            return ans

        return quick_mul(x, n) if n >= 0 else 1.0 / quick_mul(x, -n)

java：

class Solution {
    public double myPow(double x, int n) {
        return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -(long)n);
    }

    private double quickMul(double x, long n) {
        double ans = 1.0;
        // 在对 N 进行二进制拆分的同时计算答案
        while (n > 0) {
            if ((n & 1) == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x;
            }
            // 将贡献不断地平方
            x *= x;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            n >>= 1;
        }
        return ans;
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~文章来源地址https://www.toymoban.com/news/detail-453510.html

到了这里，关于算法leetcode｜50. Pow(x, n)（rust重拳出击）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！