Pascal's Triangle

https://leetcode.com/problems/pascals-triangle/description/

思路：

1. return 边界
2. 固定存入第一行[1]
3. 从第二行开始找出规律为上一行的第j个+ 第j-1个。每行的第一个和最后一个都是1.

数据结构 与 复杂度

1. ArrayList<List<Integer>> 空间为n的2次方
2. 双重for循环： 时间复杂度n的2次方

遇到的问题

1. 数组越界：
   由于判断了numRows 为1的情况，直接返回，但是导致了numRows > 1的时候，由于没有第一行的[1]，导致后面的数组越界。

public List<List<Integer>> generate(int numRows) {
        // return if < 0
        if(numRows < 1) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> ptList = new ArrayList<List<Integer>>();
        if(numRows == 1) {  //错误，无论任何情况，都应该先有这个[1] 的row
            List<Integer> row = new ArrayList<Integer>();
            row.add(1);
            ptList.add(row);
            return ptList;
        }
        
        for(int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<Integer>();
            row.add(1);
            for(int j = 1; j < i; j++) {
                row.add(ptList.get(i-1).get(j-1) + ptList.get(i-1).get(j));
            }
            row.add(1);
            ptList.add(row);
        }
        return ptList;
    }

总结

先在纸上找出规律，然后再写代码。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        // return if < 0
        if(numRows < 1) {
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> ptList = new ArrayList<List<Integer>>();
        // List<Integer> row1 = new ArrayList<Integer>();
        // row1.add(1);
        // ptList.add(row1);
        ptList.add(new ArrayList<Integer>());
        ptList.get(0).add(1);

        
        for(int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<Integer>();
            row.add(1);
            for(int j = 1; j < i; j++) {
                row.add(ptList.get(i-1).get(j-1) + ptList.get(i-1).get(j));
            }
            row.add(1);
            ptList.add(row);
        }
        return ptList;
    }
}

java 语言上犯过的错误

1. List 是接口不能初始化,

return new List<List<Integer>>(); // 错误
return new ArrayList<ArrayList<Integer>>(); //错误
return new ArrayList<List<Integer>>(); //正确

2. 不能在函数外和函数里定义同名的变量：

        List<List<Integer>> ptList = new ArrayList<List<Integer>>();
        List<Integer> row1 = new ArrayList<Integer>(); // 不能与for循环里的row重名，可以通过不创建一个变量来解决。
        row1.add(1);
        ptList.add(row1);

        
        for(int i = 1; i < numRows; i++) {
            List<Integer> row = new ArrayList<Integer>();
            row.add(1);
            for(int j = 1; j < i; j++) {
                row.add(ptList.get(i-1).get(j-1) + ptList.get(i-1).get(j));
            }
            row.add(1);
            ptList.add(row);
        }
        return ptList;