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; }};新闻热点
疑难解答
