Leetcode118_Pascal's Triangle

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

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<List<Integer>>
对于初始化第一行。对于每一行，要把第一个元素和最后一个元素赋值为1; 行内剩余元素i通过访问上一行的i和i-1.
思路不难理解，但细节多。

注意：

ArrayList 和 Array的不同: https://www.geeksforgeeks.org/array-vs-arraylist-in-java/ （一定要看！）
对于每一行，不要忘了先创建一个List（Line 9, 13, 14）,才能对其操作，如添加元素

代码：

 class Solution {

     public List<List<Integer>> generate(int numRows) {

         List<List<Integer>> triangle = new ArrayList<List<Integer>>();

         if (numRows == 0) {

             return triangle;

         }

         triangle.add(new ArrayList<>());

         triangle.get(0).add(1);

         for (int rowNum = 1; rowNum < numRows; rowNum++){

             List<Integer> row = new ArrayList<Integer>();

             List<Integer> prevRow = triangle.get(rowNum - 1);

             row.add(1);

             for(int j = 1; j < rowNum; j++){

                 row.add(prevRow.get(j-1) + prevRow.get(j));

             }

             row.add(1);

             triangle.add(row);

         }

         return triangle;

     }

 }

时间复杂度：O(numRows^2)

空间复杂度：O（numRows^2）

巴特西

Leetcode118_Pascal's Triangle_Easy

最新文章

热门文章