【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这个解法下面的一个评论（个人感觉这个解法逻辑最容易理解）