[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?

<Solution>

這題是 Pascal's Triangle 的衍生題

差別在於，這次只要回傳指定的 row of Pascal's triangle

並且，題目有要求只能使用 O(k) 的 extra space

想法如下

• 多用一個 prv vector 來儲存上次的數值

• 每次要求出目前的數值的時候，先把值存到 prv，再從 prv 算出新的值

code 如下

	class Solution {
	public:
	vector<int> getRow(int rowIndex) {
	vector<int> ans(rowIndex+1, 1);
	if(rowIndex < 2) {
	return ans;
	}
	//> extra O(k) space
	vector<int> prv(rowIndex+1, 1);
	for(int end = 2; end <= rowIndex; end++) {
	for(int start = 1; start < end; start++) {
	//> save the previous number
	prv[start] = ans[start];
	ans[start] = prv[start-1] + prv[start];
	}
	}
	return ans;
	}
	};

view raw pascalTriangleII_1.cpp hosted with ❤ by GitHub

再仔細看一下，會發現需要 extra space 是因為是用由前往後的方式來計算數值

所以前面的數值會被先更新，因此需要先記錄下來

這時候如果改成由後往前計算，這樣就不會發生需要參考的數值被改掉的情況

因此也可以省掉多使用 O(k) 的 extra space

code 如下

	class Solution {
	public:
	vector<int> getRow(int rowIndex) {
	vector<int> ans(rowIndex+1, 1);
	for(int end = 2; end <= rowIndex; end++) {
	//> calculate value from back to front
	//> in this way, no extra space is needed
	for(int start = end-1; start > 0; start--) {
	ans[start] += ans[start-1];
	}
	}
	return ans;
	}
	};

view raw pascalTriangleII_2.cpp hosted with ❤ by GitHub