【LeetCode】119. Pascal's Triangle II

问题描述

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?

求杨辉三角中索引为 k 的那一行，从示例可以看出，索引是从0开始的。

只使用O(k)空间

问题分析

杨辉三角的下一行只需要上一行就可以算出来（可参考【LeetCode】118. Pascal's Triangle），所以，只要保存好上一行就可以实现了。

代码

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> r(rowIndex+1);
        vector<int> tmp(rowIndex+1); // 临时空间
		r[0]=1;
		tmp[0]=1;
		for(int i=1;i<=rowIndex;i++) {
			int j=0;
			r[j++]=1;
			for(;j<i;j++) {
				r[j]=tmp[j-1]+tmp[j];
			}
			r[j]=1;
			for(int k=0;k<=j;k++) {
				tmp[k]=r[k];
			}
		}
		return r;   
    }
};