首页 > ACM题库 > LeetCode-Pascal’s Triangle II
2014
07-05

LeetCode-Pascal’s Triangle II

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?

链接:http://oj.leetcode.com/problems/pascals-triangle-ii/

直接上代码,先是这个比较容易理解的(>_<)空间复杂度O(1)

class Solution {
public:
	vector<int> getRow(int rowIndex) {
		if (rowIndex < 0) return vector<int>();
		vector<int> res(rowIndex + 1);
		if (rowIndex == 0)
		{
			res[0] = 1;
			return res;
		}

		int t1, t2;

		for (int i = 1; i <= rowIndex; i++)
		{
			res[0] = res[i] = 1;
			t1 = res[0];
			t2 = res[1];
			for (int j = 1; j < i; j++)
			{
				res[j] = t1 + t2;
				t1 = t2;
				t2 = res[j + 1];
			}
		}
		return res;
	}
};

然后这个就比较浓缩了,空间复杂度同样也是O(1)

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result(rowIndex+1, 1);
        for(int i=0; i<=rowIndex; i++) {
            for(int j=i-1; j>=1; j--) {
                result[j] = result[j-1] + result[j];
            }
        }
    return result;
    }
};

 

 


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }