Skip to content

LeetCode: 119-Pascal’s Triangle II 解題紀錄

題目

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

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

Example 1:Input: rowIndex = 3 Output: [1,3,3,1]

Example 2:Input: rowIndex = 0 Output: [1]

Example 3:Input: rowIndex = 1 Output: [1,1]

Constraints:

  • 0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

題目給定一個層數的 rowIndex，我們要做的就是返回帕斯卡三角形 rowIndex 層的陣列。

解題思路

帕斯卡三角形是一個很有趣的題目，我一開始很直接地用一個陣列儲存前一層，然後再用另外一個陣列存放前一個陣列的兩值相加結果 —— 想當然，這不是最好的作法。

實際上，我們可以只宣告一個陣列，並在計算每一層開始時在該陣列的結尾添加一個 1（因為每一層的最後一個數字肯定為 1），然後從倒數第二個數字 i 開始，計算 rows[i] += rows[i-1]。這樣倒著加回去也能正確地計算帕斯卡三角形，並且也不需要花費額外的記憶空間。


C++ 範例程式碼

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> rows({1});

        for (int index=0; index<rowIndex; ++index) {
            rows.emplace_back(1);

            for (int i=rows.size()-2; i>0; --i) {
                rows[i] += rows[i-1];
            }
        }

        return rows;
    }
};



Python 範例程式碼

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        # Init
        rows = [1]

        # Compute
        for index in range(rowIndex):
            rows.append(1)

            i = len(rows) - 2
            while i > 0:
                rows[i] += rows[i-1]
                i -= 1

        return rows

References

Read More

Tags:

Leave a Reply