Pow(x,n)Leetcode解决方案  


难度级别 中等
经常问 土砖 亚马逊 Apple 体位法 彭博 易趣 Facebook 高盛 谷歌 LinkedIn 微软 神谕 贝宝 尤伯杯 VMware的 沃尔玛实验室
算法 二进制搜索 编码 访谈 面试准备 力码 力码解决方案 数学

问题“ Pow(x,n)Leetcode解”指出给您两个数字,其中一个是浮点数,另一个是整数。 整数表示指数,而基数是浮点数。 告诉我们在评估基数的指数后找到值。 底数可以是负数,正数或零。 指数可以位于整数范围之间的任何位置。 我们还对输出施加了约束。 输出将介于-10000到+10000之间。 因此,让我们看一些示例。

Pow(x,n)Leetcode解决方案

使用案列  

Base: 2
Exponent: 10
Answer: 1024

说明:由于2 ^ 10的值= 104,因此得出了答案。 也可以通过重复乘以2 10次来检查。

Base: 2
Exponent: -10
Answer: 0.00098

说明:答案已更改,因为指数的值也已更改为-10。

蛮力法  

问题Pow(x,n)Leetcode解的蛮力方法非常简单。 我们只需要模拟评估指数的操作即可。 通过乘以基本指数次数可以轻松评估指数。 因此,我们可以使用我们喜欢的任何编程语言中的循环轻松地对此进行仿真。 要注意的一件事是极端情况。 当指数等于整数的最大值或整数的最小值时 整数。 当我们将指数作为整数的最小值时,答案可以是1或0。如果基数是1或-1,则将指数作为整数的最小值,则答案将为1,否则为0。类似地,我们只能有1由于输出约束小于10000,所以指数为整数的最大值。考虑到这些约束,我们可以通过模拟基本指数时间的乘积编写为蛮力代码。

参见
洪水填充LeetCode

Pow(x,n)Leetcode解决方案的代码

C ++代码

#include <bits/stdc++.h>
using namespace std;

double myPow(double x, int n) {
    if (n == INT_MAX) return x;
    else if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
    if(n<0) x=1/x, n*=-1;
    double ans = 1;
    for(int i=0;i<n;i++)
        ans = ans*x;
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static double myPow(double x, int n) {
        if (n == Integer.MAX_VALUE) return x;
        else if (n == Integer.MIN_VALUE) return (x == 1 || x == -1) ? 1 : 0;
        if(n<0) {
            x=1/x;
            n*=-1;
        }
        double ans = 1;
        for(int i=0;i<n;i++)
            ans = ans*x;
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.println(myPow(2, 10));
    }
};
1024.0

复杂度分析

时间复杂度

上), 因为我们一直循环直到乘以基本指数时间。 因此,时间复杂度是线性的。

空间复杂度

O(1), 因为我们只需要存储答案,所以我们使用单个变量。 因此,空间复杂度是恒定的。

Pow(x,n)Leetcode解的优化方法  

优化的方法使用了快速取模算法。 我们可以以递归方式或迭代方式实现快速模取幂。 在快速模幂运算中,我们将底数乘以2的幂。通过这种方式,我们意味着我们将继续自己乘以底数。 因此,在第一步中,基础将变为自身的平方。 假设用“ b”表示的基数。 因此,在第一步中,它变成b ^ 2,在下一步中,它变成b ^ 4,然后是b ^ 8,然后是b ^ 16,依此类推。 现在,我们只乘以与指数幂相对应的基本幂。 因此,将指数转换为二进制格式,并继续按照指数二进制格式乘以基数。 例如,计算3 ^ 6。 此处base = 3,exponent =6。将6转换为二进制格式后得到110。现在,在第一步中,我们检查指数是否具有1。由于6的第一个最低有效位为0,因此我们跳过了它,并减去了base变成b ^ 2。 现在,6有1作为其第二个最低有效位,因此我们将b ^ 2乘以答案。 现在答案等于b ^ 2。 然后,底数变为b ^ 2。 由于4具有6作为其最低的第三有效位,因此我们将b ^ 1乘以答案。 现在答案变为b ^ 3 * b ^ 4 = b ^ 2。 这就是我们想要的。 检查以下实现,以了解如何实现该算法。

参见
加扰字符串

Pow(x,n)Leetcode解决方案的优化代码

C ++代码

#include <bits/stdc++.h>
using namespace std;

double myPow(double x, int n) {
    if (n == INT_MAX) return x;
    else if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
    if(n<0) x=1/x, n*=-1;
    double ans = 1;
    while(n>0){
        if(n&1)
            ans *= x;
        x = x*x;
        n = n>>1;
    }
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static double myPow(double x, int n) {
        if (n == Integer.MAX_VALUE) return x;
        else if (n == Integer.MIN_VALUE) return (x == 1 || x == -1) ? 1 : 0;
        if(n<0) {
            x=1/x;
            n*=-1;
        }
        double ans = 1;
        while (n>0){
            if(n%2 == 1) ans = ans*x;
            x = x*x;
            n = n>>1;
        }
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.println(myPow(2, 10));
    }
};
1024

复杂度分析

时间复杂度

O(logN), 因为我们使用了快速对数幂运算,该运算需要对数时间来计算基数上的指数。 我们还可以直观地找到时间复杂度。 由于我们将指数除以直到它变为0。因此所需的时间取决于logN,其中N是指数。

空间复杂度

O(1), 由于我们使用单个变量来存储答案,因此空间复杂度是恒定的。