首页 > 代码库 > 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?
思路：对于Pascal三角形的每一行，其两端元素为1，而中间元素curr[i]=prev[i-1]+prev[i]。为了求得第k行，使用依次迭代求解即可。同时，利用每一行的对称性优化内循环。
1 class Solution { 2 public: 3 vector<int> getRow( int rowIndex ) { 4 if( rowIndex < 0 ) { return vector<int>( 0 ); } 5 vector<int> pascal( 1, 1 ); 6 for( int i = 1; i <= rowIndex; ++i ) { 7 vector<int> tmp_pascal( i+1, 1 ); 8 for( int k = 1; k <= i/2; ++k ) { 9 tmp_pascal[k] = tmp_pascal[i-k] = pascal[k-1] + pascal[k];10 }11 pascal = tmp_pascal;12 }13 return pascal;14 }15 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。