8-50.Pow(x,n)

• 2021 年 4 月 21 日
• 筆記
• leetcode, 二分查找

題目描述：

解題思路：

第一想法是遞歸，結果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;
        }
    }
}