iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 19
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 19

【從面試題學邏輯-19】幫你自己次方一下(leetcode 50. Pow(x, n))

題目:
請寫一個方法,來計算x的n次方

舉例:
Pow(2,3)應該要等於8

點我前往LeetCode題目


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


是的,既然我們都說這裡是遞迴單元,當然使用一般暴力解是不行的

如果我們單純用for迴圈跑這題會發生什麼事呢?

啊,他就像喝水一樣自然的爆掉了/images/emoticon/emoticon13.gif???)

我們都知道x的n次方其實是「x的(n/2)次方做平方」對吧?

所以可以利用這個特性,拿到自己(n/2)次方的結果,做平方後,就可以省下一半的時間。

class Solution {
    public double myPow(double x, int n) 
    {
        double re=0;
        if(n==0) return 1;
        if(n==1) return x;
        if(n==-1) return 1.0/x;
        re = myPow(x,n/2);
        if(n%2==1) return re*re*x;
        else if(n%2== 0) return re*re;
        else return re*re/x;
    }
}

這樣講可能還是有點模糊,我們從程式碼慢慢解釋吧!

double re=0;
if(n==0) return 1;

這裡用了一個re來準備收自己(n/2)次方的結果
那我們知道n的0次方就是1,所以上面第二行就作為n=0時的中止條件(嘿!這個應該不用再解釋對吧XD)

if(n==1) return x;
if(n==-1) return 1.0/x;

這裡要注意的是,題目有可能包含負數次方的,所以遇到負數次方時,我們就要改傳1.0/x回去。

re = myPow(x,n/2);

接著拿自己的(n/2)次方結果回來,注意這裡先別急著平方,我們要額外做一些處理

if(n%2==1) return re*re*x;
else if(n%2== 0) return re*re;
else return re*re/x;

那我們知道,2的4次方就是2的2次方做平方,那2的5次方要怎麼處理?
就是2的2次方做平方後,再乘上一個2

也就是說,這段程式碼是幫助程式在遇到奇數次方時,幫我們多乘上一個x,來避免漏掉東西。而如果n是負數的奇數,則幫我們多乘上一個(1/x)。

可能有人會好奇,上面的看起來,n似乎要是2的?次方才會正常?
其實不會,我們假設n=11吧,那程式會這樣運作:

  1. call n=5的自己
  2. call n=2的自己
  3. call n=1的自己
  4. 拿到x
  5. 拿到n=2的自己,平方後多乘自己一次
  6. 拿到n=5的自己,平方後多乘自己一次
  7. 找到答案

大家可以照上面的順序,自己想像一下過程,就可以理解為何不會產生那種問題了

解決!


上一篇
【從面試題學邏輯-18】用遞迴找子集似乎把事情搞得更難懂了……(leetcode 78. Subsets)
下一篇
【從面試題學邏輯-20】你玩過小朋友下樓梯,那有玩過小朋友上樓梯嗎?(CTCI 8.1 小朋友上樓梯)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言