首页 > 基础算法 > 模拟法 > LeetCode-Pascal’s Triangle II[模拟]
2014
11-19

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

标签: Array
分析

滚动数组。

代码1

// LeetCode, Pascal's Triangle II
// 滚动数组,时间复杂度O(n^2),空间复杂度O(n)
class Solution {
public:
	vector<int> getRow(int rowIndex) {
		vector<int> array;
		for (int i = 0; i <= rowIndex; i++) {
			for (int j = i - 1; j > 0; j--){
				array[j] = array[j - 1] + array[j];
			}
			array.push_back(1);
		}
		return array;
	}
};

Java代码:

class Solution:
    # @return a list of integers
    def getRow(self, rowIndex):
        arr = [0]*(rowIndex+1)
        arr[0] = 1
        for i in range(1, rowIndex+1):
            arr[i] = 1
            for j in range(i-1, 0, -1):
                arr[j] = (arr[j] + arr[j-1])
        return arr

相关题目
Pascal’s Triangle


  1. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  2. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  3. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  4. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  5. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  6. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  7. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  8. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  9. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!

  10. 娜娜开始多亏了喜宝帮她,要不然夏明亮还会认为娜娜是上天给的另外一个琥珀吗?而且娜娜还害了喜宝,那些帮娜娜说话的人,我好讨厌!帮娜娜说话的人是认为娜娜漂亮,认为娜娜做的没有错!没有错吗?说娜娜没有做错的都是不认真看漫画的!