LeetCode #50 Pow(x, n) 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

實作一個 pow函式 , 計算 x 的 n 次方 (換句話說,就是 Xn)

LeetCode #50 題目限制

這題的題目限制比較沒什麼重要的, n 為Integer (介於Int32的區間)

直接來看下範例吧

LeetCode #50 官方範例

第一題根本就是工程師的送分題呢,最熟悉的2的10次方 – 1024 (之後有機會再為了她出一篇文章)

來看下第三題,大家都忘光光的負次方,X的負n次方 ➔ X的n次方之一 ➔ 1/Xn


解題思路

講到次方還有什麼要注意的呢?

  • 任意數的0次方都是 1
  • X為0,則取次方沒有意義

那結合以上幾個推論,我們來實作看看

C# 解決方案

首次嘗試 – 直接迴圈

public class Solution {
    public double MyPow(double x, int n) {
        if(x == 0)
        {
            return 0.0;
        }
        else if (n == 0)
        {
            return 1.0; 
        }
        
        double res = 1;
        bool neg = n < 0;   //negative power : 負的次方
        if(neg)
        {
            n*=-1;
        }
        
        //多少次方就乘多少次,反正n為整數
        for(int i = 0;i<n;i++)
        {
            res*=x;
        }
        
        //負的次方,最後要變回幾分之一
        if(neg)
        {
            res = 1/res;
        }
        
        return res;
    }
}

看起來沒什麼問題吧? 測試範例應該也都可以過

那我們大膽地按下 Submit 吧 !

First Try Failed - Time Limit Exceeded

超過時間限制了

而且還是在這種笨笨的範例上,1的整數次方一定也是1…

你說寫法有問題嗎?就邏輯上來說還確實沒有呢

這時我們再來想一下該調整邏輯

方案1修正版

我們這時來想一下

2的8次方也就是 2*2*2*2*2*2*2*2

是不是可以寫成 22 * 22 * 22 * 22 也就是 4 的4次方

而4的4次方又可以寫成 42 * 42 也就是 16的平方

要是我們能得到16再來進行計算,是不是就不用跑這麼多次了

public class Solution {
    public double MyPow(double x, int n) {
        if(x == 0)
        {
            return 0.0;
        }
        
        double res = cal(x, n);
        return n>0 ? res : 1/res;
    }
    
    
    private double cal(double x, int n)
    {
	//Console.WriteLine("x:"+x+",n="+n);     //註1
        if (n == 0)
        {
            return 1.0; 
        }
            
        double res = cal(x*x,n/2);
        return n%2 == 0 ? res : res*x;
    }
}

大家測試時可以將註1的註解移掉,可以幫助大家理解邏輯

我們一樣拿 x = 2 ,n = 8 來計算 ( 28 )

印出Log

第五次遞迴因為n為 0,所以會回傳 1

故我們看回第四次遞迴,n為1 1不是2的倍數 (n%2 == 0),故需要res * x ➔ res為第五次遞迴迴傳的1 ➔ 回傳 1*256

其他次因為n均為2的整數,故都直接回傳

所以可以得到 256

Java解決方案

方案1

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

Python3 解決方案

方案1

def cal(x: float, n: int) -> float:
    if n == 0:
        return 1.0 

    res = cal(x*x,(int)(n/2))
    return res if n%2 == 0 else res*x

class Solution:    
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        res = cal(x, n)
        return res if n>0 else 1/res

JavaScript 解決方案

方案1

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if(x == 0)
    {
        return 0.0;
    }

    res = cal(x, n);
    return n>0 ? res : 1/res;
};

function  cal(x, n)
{
    if (n == 0)
    {
        return 1.0; 
    }

    res = cal(x*x,parseInt(n/2));
    return n%2 == 0 ? res : res*x;
}

結論

這一題都之前的 LeetCode #507 Perfect Number 一樣,看到就會很直覺寫出一個辦法

但效能都不算優良,提交會得到超時的錯誤

故如何轉念思考及變換邏輯是很重要的

"Knowledge is power."
                                                                                     Francis Bacon                     

知識就是力量,而在這題,知識不只是力量,更是「power 次方」

power in dictionary

圖片來源 : 封面圖片- Photo by Kamran Chaudhry on Unsplash

英文翻譯 – 劍橋詞典

題目連結 : Pow(x, n) – LeetCode

🧡如果這篇文章有幫上你的一點點忙,那是我的榮幸

🧡可以的話,幫我的FaceBook 粉絲專頁按個讚,我會很感謝的

✅如有任何疑問,歡迎透過留言或messenger讓我知道 !

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *