leetcode 16. 数值的整数次方（快速幂+递归/迭代）

心已赠人 2023-09-28 17:51 25阅读 0赞

实现 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  
\-104 <= xn <= 104

思路：

快速幂+递归

class Solution {
        
    public:
        double myQuick(double x,long long k){
        
            if(k==0)
                return 1.0;
            double y=myQuick(x,k/2);
            return k%2==0 ? y*y : y*y*x;
        }
        double myPow(double x, int n) {
        
            long long N=n;
            return N>0 ? myQuick(x,N) : 1.0/myQuick(x,-N);
        }
    };

快速幂+迭代：

class Solution {
        
    public:
        double myPow(double x, int n) {
        
            if(n==0)
                return 1.0;
            if(x==0)
                return 0;
            double ans=1.0;
            long long b=n; //因为int是正数时补码为本身，如果是负数补码，改变符号之后需要加1，如果传进来的是（-2）的32次方，去反之后就会超出int，所以要用long long来扩大类型
            if(n<0){
        
                x=1/x; //这里是直接先取倒数，再计算倒数的n次方
                b=-b;
            }
            while(b>0){
        
                if(b&1==1)  //如果b最后一位为1，就乘在最后的结果中，是0的话不用算到结果里
                    ans*=x;
                x*=x;
                b>>=1;  //右移运算符可以看做删除最后一位，把低位最后一个移除，高位正数补0，负数补1
            }
            return ans;
        }
    };

左移和右移运算具体内容可以看：[左移和右移的算法][Link 1]

[Link 1]: https://blog.csdn.net/weixin_51358025/article/details/110430952?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%8F%B3%E7%A7%BB%E8%BF%90%E7%AE%97&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-3-110430952.nonecase&spm=1018.2226.3001.4187