LeetCode_数组_简单_119.杨辉三角II

目录

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

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

示例 1:

输入: rowIndex = 3

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

示例 2:

输入: rowIndex = 0

输出: [1]

示例 3:

输入: rowIndex = 1

输出: [1,1]

提示:

0 <= rowIndex <= 33

进阶：

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/pascals-triangle-ii

2.思路

（1）在做本题之前，可以先了解118.杨辉三角这题，本思路在该题思路1的基础上修改返回值即可。

（2）本思路来自本题LeetCode官方题解。

3.代码实现（Java）

//（1）思路1
public List<Integer> getRow(int rowIndex) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    for(int i=0;i<=rowIndex;i++){
        //保存第i行的结果，此处是从i=0行开始
        List<Integer> tmpRes = new ArrayList<Integer>();
        for(int j=0;j<=i;j++){
            if(j==0 || j==i){
                //设置杨辉三角两条腰上的值，即全部设置为1
                tmpRes.add(1);
            }else{
                //设置杨辉三角内部的值，任意一个内部的值都等于与其上一行相邻的两个值之和
                tmpRes.add(res.get(i-1).get(j)+res.get(i-1).get(j-1));
            }
        }
        //将第i行的结果保存到res中
        res.add(tmpRes);
    }
    //返回杨辉三角的第rowIndex行
    return res.get(rowIndex);
}
           

//思路2
public List<Integer> getRow(int rowIndex) {
    List<Integer> row = new ArrayList<Integer>();
    row.add(1);
    for (int i=1;i<=rowIndex;i++){
        row.add((int)((long)row.get(i-1)*(rowIndex-i+1)/i));
    }
    return row;
}