給定一個非負索引 k，其中 k ≤ 33，回傳楊輝三角的第 k 行，
在楊輝三角中，每個數是它左上方和右上方的數的和，
示例:
輸入: 3
輸出: [1,3,3,1]
進階：
你可以優化你的演算法到 O(k) 空間復雜度嗎？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/pascals-triangle-ii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路：
優化演算法到O（K）空間復雜度，關鍵在于用好楊輝三角的公式，即前者與后者的比與公式有關，步驟如下：
- 獲取楊輝三角的指定行
- 直接使用組合公式C(n,i) = n!/(i!*(n-i)!)
- 則第(i+1)項是第i項的倍數=(n-i)/(i+1);
代碼如下：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ans;
long cur = 1;
for(int i = 0; i <= rowIndex; i ++) {
ans.push_back((int)cur);
// 注意這里有運算子先后問題，要先乘再除！
cur = cur * (rowIndex - i) / (i + 1);
}
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259144.html
標籤：其他