Pow(x,n)Leetcode解決方案  


難度級別 中烘焙
經常問 土磚 亞馬遜 蘋果 體位法 彭博社 易趣 Facebook 高盛 谷歌 LinkedIn Microsoft微軟 神諭 貝寶 尤伯杯 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,因此我們跳過它並減去基數。變成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), 由於我們使用單個變量來存儲答案,因此空間複雜度是恆定的。