118. Pascal's Triangle

我不是女神ヾ 2022-06-13 11:21 141阅读 0赞

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,  
Return

[
         [1],
        [1,1],
       [1,2,1],
      [1,3,3,1],
     [1,4,6,4,1]
    ]

问题描述：给定一个数，产生这个数的杨辉三角，即产生的杨辉三角的行数为给定的数字。

分析：杨辉三角的思路很简单，每一行的第一个元素和最后一个元素为1，其他对应位置的元素等于上一行对应位置的值和前一个位置对于的元素之和。

行数numRows表示每行元素的个数，可分以下两种情况：

（1）当行数numRows为1或为2时，可单独处理，直接赋值为1；

（2）当行数numRows大于等于3时，每行的元素根据上一行对应的元素获得。注意list的值从0开始，而numRows从1开始，所以获取上一行的list的索引值为listofList.get(i-2)。

public class Solution {
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> listofList = new ArrayList<List<Integer>>();
            
            for(int i = 1;i <= numRows;i++){
                List<Integer> list = new ArrayList<Integer>();
                if(i == 1){
                    list.add(1);
                    listofList.add(list);
                }
                if(i == 2){
                    list.add(1);
                    list.add(1);
                    listofList.add(list);
                }
                if(i>=3){
                    for(int j = 0;j < i;j++){
                        List<Integer> list1 = new ArrayList<>();
                        if(j == 0 || j == i-1)
                            list.add(1);
                        else{
                            list1 = listofList.get(i-2);
                            list.add(list1.get(j-1)+list1.get(j));
                        }
                    }  
                    listofList.add(list);
                }
            }
            return listofList;
        }
    }