题目描述：

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 3
输出: [1,3,3,1]

解法一：从后往前   末尾添0是关键

空间复杂度是O(k)

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list=new ArrayList<Integer>();
        if(rowIndex<0)
            return list;
        for(int i=0;i<=rowIndex;i++)
        {
            if(i==0)
                list.add(1);
            else
                list.add(0);//是关键
            for(int j=i;j>0;j--)
            {
                list.set(j,list.get(j-1)+list.get(j));
            }
        }
        return list;
    }
}

解法二：

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        List<Integer> list=new ArrayList<Integer>();
        if(rowIndex<0)
            return list;
        for(int i=0;i<=rowIndex;i++)
        {
            list=new ArrayList<Integer>();
            list.add(1);
            for(int j=1;j<i;j++)
            {
                list.add(result.get(i-1).get(j-1)+result.get(i-1).get(j));
            }
            if(i>=1)
                list.add(1);
            result.add(list);
        }
        return result.get(rowIndex);
    }
}

使用滚动数组进一步优化空间复杂度

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
        {
            List<Integer> cur=new ArrayList<Integer>();
            cur.add(1);
            for(int j=1;j<i;j++)
                cur.add(pre.get(j-1)+pre.get(j));
            if(i>=1)
                cur.add(1);
            pre=cur;
        }
        return pre;
    }
}

 

没有想到

List<List<Integer>> result=new ArrayList<List<Integer>>();

List<Integer> list=new ArrayList<Integer>();

光只考虑了List<Integer> list=new ArrayList<Integer>();