首页 > 基础算法 > 模拟法 > 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