【LeetCode-Java實作】118. Pascal's Triangle

118. Pascal's Triangle

• 題目描述
• 解題思路
• 實作代碼

題目描述

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

楊輝三角形：第i行第j個元素值=第i-1行第j-1個元素值+第j個元素值

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5

Output:

[

1,

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1]

]

給定總行數，最後需要輸出所有行的元素（使用list的嵌套結構進行輸出）

解題思路

思路很簡單，先分别求出每一行的元素，再把所有行的元素輸出。

1. 建立一個list用來存放所有的行；

2. 再建立numRows個list用來存放每一行的元素

   （在循環中建立，每次循環建立一個list存放某一行元素，再把這個list放入到總的list中）；

3. 确定每一行元素：

   首先每一行第一個和最後一個都是1，

   剩下的即符合：第i行第j個元素值=第i-1行第j-1個元素值+第j個元素值

實作代碼

根據上述思路可得Java代碼：.

public List<List<Integer>> generate1(int numRows) {
        //allrows存放所有行的元素，嵌套list的list---可以了解為外部list 
        List<List<Integer>> allrows = new ArrayList<List<Integer>>(); 
        
        //循環從第一行開始，到第numRows行
        for(int i = 1; i <= numRows; i++) {     //每一行都是一層循環，算出每一行的所有元素
            //row存放每一行的元素
            List<Integer> row = new ArrayList<Integer>();  
            for(int j = 1; j <= i; j++) {      //每一行元素個數=第幾行數，是以用j==i代表每行最後一個元素
                if(j == 1 || j == i) {         //每一行第一個和最後一個元素都是1
                	row.add(1);
                } else {
                    //第i行第j個元素值=第i-1行第j-1個元素值+第j個元素值
                    //get(i-2)  (j-2)是因為list的下标從0開始,而i,j為了易于了解都是從1開始的，是以需要減去2
                	row.add(allrows.get(i - 2).get(j - 2) + allrows.get(i - 2).get(j - 1)); 
                }
            }
            allrows.add(row);    //每求出一行，就把結果加入到allrows裡
        }
     return allrows;   
    }
           

參考

參考https://leetcode.com/problems/pascals-triangle/discuss/38141/My-concise-solution-in-Java這個解法下面的一個評論（個人感覺這個解法邏輯最容易了解）