LeetCode119 Pascal's Triangle II Pascal三角形II

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

题源：here；完整实现：here

思路：

为了满足空间上的限制，我们对一个vector进行迭代更新，每次往后面舔1，然后按照Pascal三角形的规则进行迭代：当前位置的值是该位置之前的值加上该位置前一个位置的值。

vector<int> getRow(int rowIndex) {
	vector<int> v;
	for (int i = 0; i <= rowIndex; i++){
		v.push_back(1);
		if (i <= 1) continue;
		int pre = 1;
		for (int j = 1; j < v.size() - 1; j++){
			int temp = v[j];
			v[j] = pre + v[j];
			pre = temp;
		}
	}

	return v;
}

纪念贴图：