首页 > 代码库 > leetcode_119 Pascal's Triangle II (Array)

leetcode_119 Pascal's Triangle II (Array)

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?

输出杨辉三角的第k行

key:由于只能使用O(k)的空间,只能使用一维数组滚动计算。A[k][n]=A[k-1][n-1]+A[k-1][n]

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list=new ArrayList<>();
        if (rowIndex==0){
            list.add(0,1);
        }else{
            list.add(0,1); //第一位为1
            for(int i=1;i<=rowIndex;i++){
                list.add(i,1); //第i行的最后一位为1
                for(int j=i-1;j>0;j--){
                    list.set(j,list.get(j)+list.get(j-1));
                }
            }
        }
        return list;
    }
}

由于ArrayList中的 set()和add()方法弄混了,困扰了好久才发现错误。

技术分享

技术分享

技术分享

 

 

  

leetcode_119 Pascal's Triangle II (Array)