LeetCode每日一题：杨辉三角

首先看看最容易想出来的暴力解法把，思路就是用两个嵌套的for循环来生成数组
这里需要用到pre来存上一个数组，用于计算当前数组的值，还是非常简单的

• 代码：

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

这都能超过百分之77的用户我是没想到的

第二种解法：取巧解法(每次看别人的解法都会觉得我是个沙雕）

解题思路

观察一下规律，发现当前一行只比上一行多了一个元素，最最关键的一点：本行元素等于上一行元素往后错一位再逐个相加：

• 代码;

  class Solution {
public List<List<Integer>> generate(int numRows) {        
    List<List<Integer>> res = new ArrayList<>();
    if(numRows == 0) return res;
    List<Integer> firstRow = new ArrayList<>();
    firstRow.add(1);
    res.add(new ArrayList(firstRow));
    int size = res.size();
    while(size < numRows){
        LinkedList<Integer> first = new LinkedList<>();
        first.addFirst(0);
        LinkedList<Integer> second = new LinkedList<>();
        second.addLast(0);
        for(int x: res.get(size-1)){
            first.addFirst(x);
            second.addLast(x);
        }
        List<Integer> newRow = new ArrayList<>();
        for(int i=0; i<first.size(); i++){
            newRow.add(first.get(i) + second.get(i));
        }
        res.add(newRow);
        size++;
    }
    return res;
}
}