­

8-50.Pow(x,n)

題目描述:
image
解題思路:

第一想法是遞歸,結果f(x,n) = x * f(x,n-1);這種方法的空間複雜度太高了,太想當然。

看了下題解:採取分治的方法:f(x,n) = f(x,n/2) * f(x,n/2);這裡只需要注意一下n的奇偶性就可以,如果是偶數,就是這個式子,如果是奇數,需要額外多乘一個x;這樣空間複雜度就從O(N)轉成了O(logN);

主要是分治和遞歸

程式碼:

class Solution {
    public double myPow(double x, int n) {
        long N = n;//當n是-intMIN的時候,轉換成正數會溢出、常用的辦法是轉成long類型的數據
        //處理一些特殊情形
        if(x == 0){
            return 0;
        }
        if(N == 0){
            return 1;
        }
        if(N > 0){
            return powHelper(x,N);
        }else{
            return 1.0/powHelper(x,-N);
        }
    }
    public double powHelper(double x,long N){
        if(N == 1){//定義該函數出口
            return x;
        }
        //分解成奇數和偶數兩個子問題,然後進行遞歸
        if(N % 2 == 0){//當n為偶數
            double half = powHelper(x,N/2);
            return half * half;
        }else{//n為奇數
            double half = powHelper(x,N/2);
            return half * half * x;
        }
    }
}