算法leetcode｜50. Pow(x, n)（rust重拳出击）

文章目录

50. Pow(x, n)：

实现

pow(x, n)

，即计算 x 的整数 n 次幂函数（即，xn ）。

样例 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/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n 是一个整数
• -104 <= xn <= 104

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 直接想到的就是模拟，x循环n - 1次乘以x，但是会非常慢。
• 还得是快速幂：xn = xn / 2 * xn / 2。
• 需要注意的一点是题目的参数n都是int / i32，一般就是32位有符号整数，有个坑，它的取值范围是【-2147483648，2147483647】，所以如果传参是 -2147483648，直接取反就悲剧了。

#include<iostream>intmain(){int n = INT_MIN;//    -2147483648//    -2147483648//    2147483648
    std::cout << n << std::endl <<-n << std::endl <<-(long)n;return0;}

题解：

rust：

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

go：

funcmyPow(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{returnquickMul(x, n)}else{return1.0/quickMul(x,-n)}}

c++：

classSolution{private:doublequickMul(double x,longlong 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:doublemyPow(double x,int n){return n >=0?quickMul(x, n):1.0/quickMul(x,-(long)n);}};

python：

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

        return quick_mul(x, n)if n >=0else1.0/ quick_mul(x,-n)

java：

classSolution{publicdoublemyPow(double x,int n){return n >=0?quickMul(x, n):1.0/quickMul(x,-(long)n);}privatedoublequickMul(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/ 博客原创~