[LeetCode 筆記] 118. Pascal's Triangle

leetcode pascal's triangle java python algorithm

Chris 2023-05-28 21:41:06 ‧ 1249 瀏覽

分享至

前言

　　這題的大方向是要如何找到上一行的上一列的元素來做兩兩相加的運算，像是動態規劃的邏輯思考，需要用到雙迴圈的關係，時間複雜度達 O(n²)，這裡有 JAVA 和 Python 的寫法。

題目

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:

給定一個整數 numRows，回傳一個相對應層數的帕斯卡三角形。
在帕斯卡三角形裡遍歷的每個數字，都是其上方兩個數的合：

Pascal's Triangle

題目連結：https://leetcode.com/problems/pascals-triangle/

題目限制

1 <= numRows <= 30

範例

Input: numRows = 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Input: numRows = 1
Output: [[1]]

思路&筆記

這題的大方向是要如何找到上一行的上一列的元素來做兩兩相加的運算，像是動態規劃的邏輯思考。

首先我們把帕斯卡三角形想像成一個大型的 List，再把這個大型的 List 裡的每個元素放入個別 List 裡來當作每一列。

已經有了兩個要件，接著用雙迴圈去遍歷大型的 List 裡的每一列放我們要放的元素。

可是不要忘了要判斷每一列的頭跟尾都要是 1 才能把對的元素放在對位置。

解決頭尾已經是 1 了，再把前一列的兩值加起來後依依放進去。 (這邊要注意，因我們用的是 ArrayList 類，需要用 .get() 方法來取得元素的位置)

最後把每一列放入大型的 List 裡。

JAVA 實現

class Solution {
    public List<List<Integer>> generate(int numRows) {

        // 創建二維列表
        List<List<Integer>> nums = new ArrayList<List<Integer>>();

        // 為了防止無效輸入，直接回傳一個空的列表
        if (numRows <= 0){
            return nums;
        }
        
        for (int i=0; i<numRows; i++){
            // 每一列
            List<Integer> row = new ArrayList<Integer>();
            // 如果第一行要生成數字，j<i => 0<0 無法成立，i 應要 +1
            for(int j=0; j<i+1; j++){ 
                // 判斷 list 的頭尾 (到了第5行要總生成5個數字，最後一個數字)
                if (j==0 || j==i){
                    row.add(1); // 是 0 的話插入 1
                }else {
                    // 因要從二維列表取值，從第 i-1 行中取得第 j-1 的元素
                    row.add(nums.get(i-1).get(j-1) + nums.get(i-1).get(j)); // 把前一列的兩值加起來
                }
            }
            nums.add(row); // 把列表插入二維列表
        }
        return nums;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        nums = [] # 大三角形
        for i in range(numRows):
            row = [] # 每行
            for j in range(len(nums)+1):
                if j==0 or j==i: # 判斷頭尾
                    row.append(1)
                else:
                    row.append(nums[i-1][j-1] + nums[i-1][j]) # 把前一列的兩值加起來
            nums.append(row)
        return nums