LeetCode #118 Pascal’s Triangle 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Pascal's Triangle Example (gif)

中文翻譯

給予一個整數 numRows,回傳巴斯卡三角形的前numRows

在巴斯卡三角形裡,每一個數字都會是前兩個數字的加總,如下圖所示(上面那張gif)

LeetCode #118 Constraints

題目限制則為最高列數為30

來看下官方的範例

LeetCode #118 Example Picture

可以直接看向上面的那個gif,陣列的各個子陣列分別就對應到了三角形的各列

分別是1到5列,跟只有1列的區別


解題思路

看到兩數相加等於下一數的,是不是感覺到很熟悉呢

還記得之前提過的 LeetCode #70 爬梯子費波那契數嗎? 巴斯卡三角形其實就是他的變形呢!

這次也採用與上次類似的作法,不過因為要儲存在陣列裡面

所以可以省下一點暫存的麻煩,直接拿陣列值就好

來看一下程式吧

C# 解決方案

方案1

public class Solution {
    public IList<IList<int>> Generate(int numRows) {
        List<List<int>>res = new List<List<int>>();
        
        
        res.Add(new List<int>(){1});   //巧婦難為無米之炊,第一列的值容我寫死
        
        if(numRows!=1)  //超過第一列才要計算,合情合理吧?
        {
            for(int i = 1;i<numRows;i++)
            {
                List<int>tmp = new List<int>();  //暫存子陣列
                for(int j=0;j<=i;j++)
                {
                    int num;
                    if(j==0 || j==i)   //每列第一跟最後的數字都是1,沒甚麼好說的
                    {
                        num = 1;
                    }
                    else
                    {
                        num = res[i-1][j-1]+res[i-1][j];
                    }
                    tmp.Add(num); 
                }
                res.Add(tmp);  //加回母陣列
            }
        }
        
        return res.ToArray();
        
    }
}

注意上面的 i 代表的是每一列,j 則是每列中的各個數字

可以看到計算就是拿上面一列的,自已index前一個跟自己index的加總,就會是目前欄位的值

Java解決方案

方案1

class Solution {
    public List<List<Integer>> generate(int numRows) {
        
        List<List<Integer>>res = new ArrayList<List<Integer>>();
        
        res.add(Arrays.asList(new Integer[]{1}));
        
        if(numRows!=1)
        {
            for(int i = 1;i<numRows;i++)
            {
                List<Integer>tmp = new ArrayList<Integer>();
                for(int j=0;j<=i;j++)
                {
                    int num;
                    if(j==0 || j==i)
                    {
                        num = 1;
                    }
                    else
                    {
                        num = res.get(i-1).get(j-1)+res.get(i-1).get(j);
                    }
                    tmp.add(num);
                }
                res.add(tmp);
            }
        }
        
        return res;
    }
}

運行時間 : 1ms

Python3 解決方案

方案1

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        
        res = [];
        res.append([1]);
        
        if numRows!=1:
            for i in range(1,numRows):
                tmp = [];
                for j in range(0,i+1):
                    if j==0 or j==i :
                        tmp.append(1);
                    else:
                        tmp.append(res[i-1][j-1]+res[i-1][j]);
                        
                res.append(tmp);
                
        return res;

JavaScript 解決方案

方案1

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    var res = [];
    res[0] = [1];
    
    if(numRows!=1)
    {
        for(let i = 1;i<numRows;i++)
        {
            let tmp = [];
            for(let j=0;j<=i;j++)
            {
                var num;
                if(j==0 || j==i)
                {
                    num = 1;
                }
                else
                {
                    num = res[i-1][j-1]+res[i-1][j];
                }
                tmp[j] = num;
            }
            res[i] = tmp;
        }
    }
    return res;
};

結論

整體上來說,這題算是比較沒有難度的

但在寫過費波那契數後,不由得感嘆數學家的腦袋

不過是東方還西方,聰明人的想法往往很相似啊

"你知道嗎?   巴斯克起司蛋糕是從巴斯克地區(西班牙及法國)來的喔"
                                                                                    維基百科說的                   

⬆原來巴斯克是地名啊…

附上個巴斯卡三角形的好朋友,巴斯克起司蛋糕?

巴斯克起司蛋糕

圖片來源 : 蛋糕 – Photo by Syauqy Ayyash on Unsplash

題目連結 : Pascal’s Triangle – LeetCode

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

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

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

最新文章

發佈留言

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