首页 > 代码库 > Leetcode-Pascal's Triangle II

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

 

Solution:

public class Solution {    public List<Integer> getRow(int rowIndex) {        List<Integer> preRow = new ArrayList<Integer>();        List<Integer> curRow = new ArrayList<Integer>();                curRow.add(1);        int len;        for (int i=1;i<=rowIndex;i++){            preRow = curRow;            curRow = new ArrayList<Integer>();            len = i+1;            //j==0            curRow.add(1);            //j==1 to (len-2)            for (int j=1;j<len-1;j++)                curRow.add(preRow.get(j-1)+preRow.get(j));            //j==len-1            curRow.add(1);        }                return curRow;    }}

递推问题。只需存当前行和上一行就行。

Leetcode-Pascal's Triangle II