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)会在每次进入第一次循环后判断一次。本着减少资源消耗的原则，应当提到外面。