over 1 year ago

問題描述

#50.Pow(x, n)

func myPow(x float64, n int) float64 {
  
}

難度中
實作次方函數Pow(x,n),
若以數學式表示如下

解題思路

在這裡我們會用到次方函數以下幾點特性

  1. 任意數的0次方,皆等於1
  2. x的-1次方會等於1/x
  3. 次方數是可以加總的 根據特性1, 我們已經可以寫出第一行代碼了,如下
    if n==0{
        return 1
    }
    
    接著我們要來處理n為負數的情境,由特性2可知若n為負數時,可將x轉換為倒數, 代碼表示如下
    if n<0{
        x=1/x //x轉換為倒數
    
        n=-n  //n轉換為正數
    
    }
    

最後一步,使用遞迴開始運算,以數學式(1)表示

程式碼實作如下,

if n==0{
        return 1
    }
if n<0{
    x=1/x
    n=-n
  }
return x*myPow(x,n-1) //遞迴,n每次減1直到n=0時回傳結果

現在可以將代碼提交到LeetCode,按下右下角Submit Solution,LeetCode會自動幫你跑測試,如果沒有意外的的話,你應該會出現 Time Limit ExceededMemory Limit Exceeded等錯誤訊息.

表示在x=0.00001, n=2147483647程式運算太久或是發生了Stack Overflow!!!

現在我們要來改善這個問題,別忘了我們還有特性3還沒使用,我們將利用次方加總的特性減化運算過程, 將數學式(1)修改為

如此一下程式效能將大幅提升, 程式碼如下,

if n==0{
        return 1
    }
if n<0{
    x=1/x
    n=-n
  }
  

if n%2==0 {
        return myPow(x*x,n/2)
    }
return x*myPow(x*x,n/2) //由於n是Int,所以(n-1)/2與n/2結果會是相同

最後再重新提交一次吧


所以測試均通過,點擊More Details可以查看更多資訊

如上圖,我們通過300個test case,運行時間3ms, 打敗6.25%Golang的使用者,更多細節可以自己玩玩看
Go版本完整程式碼

Scala實作

 
  def myPow(x:Double,n:Long):Double={

    n match {
      case 0=>1
      case i if i<0=>myPow(1/x,-n) //與Go最大差別在於Scala無法對變數reassign,因此直接跑遞迴
      case i if i%2==0=>myPow(x*x,n/2) 
      case _=> x* myPow(x*x,n/2)
    }


  }

Scala版本完整程式碼

← LeetCode 解題筆記(1)- 什麼是LeetCode? [30天學會Scala]Day2-函數宣告 →