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

谁借莪１个温暖的怀抱￠ 2023-10-06 19:13 36阅读 0赞

#### 目录 ####

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

## 1.题目 ##

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。  
在「杨辉三角」中，每个数是它左上方和右上方的数的和。  
![在这里插入图片描述][eedbd21bdc9d409280ba05294c8b6b79.gif_pic_left]  
**示例 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.杨辉三角][118.]这题，本思路在该题思路 1 的基础上修改返回值即可。

（2）线性递推  
本思路来自[本题LeetCode官方题解][LeetCode]。

相关题目：  
[LeetCode\_杨辉三角\_简单\_118.杨辉三角][118.]

## 3.代码实现（Java） ##

//思路1————找规律
    class Solution {
        
    	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————线性递推
    class Solution {
        
    	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;
    	}
    }

[eedbd21bdc9d409280ba05294c8b6b79.gif_pic_left]: https://img-blog.csdnimg.cn/eedbd21bdc9d409280ba05294c8b6b79.gif#pic_left
[118.]: https://blog.csdn.net/weixin_43004044/article/details/120139185
[LeetCode]: https://leetcode-cn.com/problems/pascals-triangle-ii/solution/yang-hui-san-jiao-ii-by-leetcode-solutio-shuk/