LeetCode #50 Pow(x, n) 解題思路及翻譯 - Zyrastory-當程式碰上美食

內容目錄

LeetCode題目翻譯

英文原文如下

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

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

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

直接來看下範例吧

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

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

解題思路

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

任意數的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 吧 !

超過時間限制了

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

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

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

方案1 – 修正版

我們這時來想一下

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

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

而4的4次方又可以寫成 4² * 4² 也就是 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 來計算 ( 2⁸ )

第五次遞迴因為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 次方」

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

英文翻譯 – 劍橋詞典

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

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

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

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

LeetCode題目翻譯

解題思路

C# 解決方案

Java解決方案

Python3 解決方案

JavaScript 解決方案

結論

發佈留言 取消回覆

發佈留言取消回覆