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;
}