首页 > 代码库 > 119. Pascal's Triangle II(LeetCode)

119. Pascal's Triangle II(LeetCode)

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?

class Solution {
public:
	vector<int> getRow(int rowIndex) {
		vector<int> vet1 = {1};
		vector<int> vet2 = {1,1};
		if (rowIndex == 0)
			return vet1;
		if (rowIndex == 1)
			return vet2;
		for (int i = 2; i <= rowIndex; i++)
		{
			if (i % 2 == 0)
			{
				vet1.clear();
				vet1.push_back(1);
				for (int i = 0; i < vet2.size() - 1; i++)
				{
					vet1.push_back(vet2[i] + vet2[i + 1]);
				}
				vet1.push_back(1);
			}
			else
			{
				vet2.clear();
				vet2.push_back(1);
				for (int i = 0; i < vet1.size() - 1; i++)
				{
					vet2.push_back(vet1[i] + vet1[i + 1]);
				}
				vet2.push_back(1);
			}
			
		}
		if (rowIndex % 2 == 0)
		{
			return vet1;
		}
		else
			return vet2;
		
	}
};

  别人的:

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

  

119. Pascal's Triangle II(LeetCode)