leetcode119-杨辉三角II

原题

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

leetcode119-杨辉三角II
在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

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

进阶:

你可以优化你的算法到 O(k) 空间复杂度吗?

解法

思想

可以利用leetcode118-杨辉三角中的函数来解决。

代码

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList();
        list.add(1);
        if(rowIndex == 0) return list;
        return getRowByPrev(rowIndex,getRow(rowIndex-1));
    }
    //通过上一行计算第n行
    public List<Integer> getRowByPrev(int n,List<Integer> nums){
        List<Integer> ret = new ArrayList();
        ret.add(1);
        for(int i=1;i<(n+2)/2;i++){
            ret.add(nums.get(i-1)+nums.get(i));
        }
        int size = (n+1)/2;
        for(int i=0;i<size;i++){
            ret.add(ret.get(size-i-1));
        }
        return ret;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode119-%e6%9d%a8%e8%be%89%e4%b8%89%e8%a7%92ii/

发表回复

登录后才能评论