您好,登錄后才能下訂單哦!
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?
代碼如下:(使用雙數(shù)組處理,未優(yōu)化版)
class Solution { public: vector<int> getRow(int rowIndex) { vector<int> curVec; vector<int> nextVec; if(rowIndex < 0) return curVec; for(int i = 0;i <= rowIndex; i++) { for(int j = 0;j<=i;j++) { if(j == 0) nextVec.push_back(1); else { if(j >= curVec.size()) nextVec.push_back(curVec[j-1]); else nextVec.push_back(curVec[j] + curVec[j-1]); } } curVec.swap(nextVec); nextVec.clear(); } return curVec; } };
使用思路:
The basic idea is to iteratively update the array from the end to the beginning.
從后到前來更新結(jié)果數(shù)組。
參考自:https://discuss.leetcode.com/topic/2510/here-is-my-brief-o-k-solution
class Solution { public: vector<int> getRow(int rowIndex) { vector<int> result(rowIndex+1, 0); result[0] = 1; for(int i=1; i<rowIndex+1; i++) for(int j=i; j>=1; j--) result[j] += result[j-1]; return result; } };
2016-08-12 10:46:10
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。