Given an index k, return the kth row of the Pascal’s triangle.
For example, given k = 3, Return [1,3,3,1].
Note: Could you optimize your algorithm to use only O(k) extra space?
s思路： 1. 假設我們需要k=5,我們已經得到k=4的樣子，即：[1,3,3,1,1],如何從k=4計算除k=5?我們知道[3,3]都要使用兩次，從左往右遍歷時，1+3=4需要放在3這個位置，但3還要使用一次，所以不能放。也就是說我們需要額外的空間來hold計算結果；由于3使用的次數固定，即：1+3，還有3+3,但是計算順序是1+3先進行還是3+3先進行都無所謂。所以，我們讓3+3先進行看看，即：從右往左遍歷：3+3結果為6，直接放在原來3的位置，1+3=4也直接放在3的位置。 2. 一個小trick。遍歷順序從左往右—->從右往左。但是里面的深的含義還是有趣味！
[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]class Solution {public: vector<int> getRow(int rowIndex) { // vector<int> res(rowIndex+1,1); for(int i=1;i<rowIndex;i++){ for(int j=i;j>=1;j--){ res[j]+=res[j-1]; } } return res; }};新聞熱點
疑難解答
