Leetcode 118:Pascal's Triangle 楊輝三角

118:Pascal's Triangle 楊輝三角

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

給定一個非負整數 numRows，生成楊輝三角的前 numRows 行。

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]
]           

解題思路：

​ 第一行第二行都是1，每行第一個和最後一個都為1，假設其他位置的數x索引坐标是(m,n)，則x就是數是它 索引正上方的數和索引正上方的左邊的數 之和。即(m-1,n),(m-1,n-1)兩數和。

java：

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        if(numRows == 0) return triangle;
        List<Integer> one = new ArrayList<Integer>();
        one.add(1);
        triangle.add(one);
        if(numRows == 1) return triangle;
        for (int i=1;i<numRows;i++){
            List<Integer> row = new ArrayList<Integer>();
            row.add(1);
            for (int j=1;j<i;j++){
                List<Integer> prev = triangle.get(i-1);
                row.add(prev.get(j-1)+prev.get(j));
            }
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }
}           

python：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows==0:return []
        triangle=[[1]]
        if numRows==1: return triangle
        for i in range(1,numRows):
            tmp=[1]
            for j in range(1,i):
                tmp.append(triangle[i-1][j-1]+triangle[i-1][j])
            tmp.append(1)
            triangle.append(tmp)
        return triangle
           

總結：

很簡單的一道題，可以複習一下java嵌套數組資料結構。另外 可以在内層循環加判斷

if(i!=0) row.add(1);triangle.add(row);

在i不等于0時才加上1，這樣可省略

List<Integer> one = new ArrayList<Integer>();
        one.add(1);
        triangle.add(one);
        if(numRows == 1) return triangle;           

代碼段，但是這個

if(i!=0)

會在每次進入第一次循環後判斷一次。本着減少資源消耗的原則，應當提到外面。