Last Updated on 2023-10-16 by Clay
題目
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