LeetCode每日一题5月11日 LeetCode50.Pow(x, n)

系统管理员 2023-03-13 05:22 20阅读 0赞

## 问题描述： ##

实现 [pow(*x*, *n*)][pow_x_n] ，即计算 x 的 n 次幂函数。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/powx-n

示例 1:

输入: 2.00000, 10
    输出: 1024.00000

示例 2:

输入: 2.00000, 10
    输出: 1024.00000

示例 3:

输入: 2.00000, -2
    输出: 0.25000
    解释: 2-2 = 1/22 = 1/4 = 0.25

## 解题思路： ##

按照我们常规思路，会超时

class Solution {
    public:
        double myPow(double x, int n) {
            if(x==0) return 0;
            if(n==0) return 1;
            int flag;
            if(n>0) flag=1;
            else flag=-1;
            n = abs(n);
            double res = 1;
            for(int i=1;i<=n;i++){
                res = res*x;
            }
            if(flag==1){
                return res;
            }else{
                return 1/res;
            }
        }
    };

这种情况会超时，所以我们考虑一下二分法

使用折半计算，每次把n缩小一半，这样n最终会缩小到0，任何数的0次方都为1，这时候我们再往回乘，如果此时n是偶数，直接把上次递归得到的值算个平方返回即可，如果是奇数，则还需要乘上个x的值

**例如pow(2,7),res=1.0,初始x=2，n=7**

**step1 n=7 (n%2==1 res\*=x)   x=x\*x   x=4  n=n/2**

**step2 n=3 (n%2==1 res\*=x)   x=x\*x   x=16 n=n/2**

**step3 n=1 (n%2==1 res\*=x)   x=x\*x   x=256 n=n/2**

**n = 2\*4\*16=2^7;**

**pow(2,4),res=1.0,初始x=2，n=4**

**step1 n=4 n%2==0  x=x\*x  x=4 n=n/2**

**step2 n=2 n%2==0  x=x\*x  x=16 n=n/2**

**step3 n=1 (n%2==1 res\*=x)  x=x\*x  x=256 n=n/2**

**n = 1\*16 = 2^4**

class Solution {
    public:
        double myPow(double x, int n) {
            if(x==0) return 0;
            if(n==0) return 1;
            double res = 1.0;
            int flag = -1;
            if(n>0) flag = 1;
            while(n!=0){
                if(n%2!=0){
                    res*=x;
                }
                x*=x;
                n=n/2;
            }
            return flag>0?res:1/res;
            
        }
    };

[pow_x_n]: https://www.cplusplus.com/reference/valarray/pow/