leetCode 119. Pascal's Triangle II 数组

简介:

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?

代码如下:(使用双数组处理,未优化版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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.

从后到前来更新结果数组。

参考自:https://discuss.leetcode.com/topic/2510/here-is-my-brief-o-k-solution

1
2
3
4
5
6
7
8
9
10
11
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


本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1837189

相关文章
|
30天前
|
算法
【数组相关面试题】LeetCode试题
【数组相关面试题】LeetCode试题
|
1月前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
21 0
|
1月前
|
人工智能 BI
力扣561 数组拆分
力扣561 数组拆分
|
30天前
|
存储 算法
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
|
30天前
|
存储
力扣刷题-最大子数组和
力扣刷题-最大子数组和
9 1
|
30天前
leetcode2967. 使数组成为等数数组的最小代价
leetcode2967. 使数组成为等数数组的最小代价
20 0
|
1月前
|
算法 搜索推荐
LeetCode刷题---215. 数组中的第K个最大元素(双指针,快速选择)
LeetCode刷题---215. 数组中的第K个最大元素(双指针,快速选择)
|
1月前
|
Go C++
【力扣】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
【2月更文挑战第17天】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
29 8
|
1月前
|
算法 测试技术 索引
力扣面试经典题之数组/字符串(二)
力扣面试经典题之数组/字符串(二)
13 0
|
1月前
|
存储 算法 语音技术
【数据结构与算法】力扣刷题记之 稀疏数组
【数据结构与算法】力扣刷题记之 稀疏数组