118. Pascal's Triangle杨辉三角形（全部/一行）

［抄题］：

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]
]

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

要返回数据结构的，先新建确保类型了再cc

［奇葩corner case］：

［思维问题］：

不知道怎么表示

［一句话思路］：

做好每一行后再放进去

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

不熟悉双重嵌套：内部数组处理完了要加到外部数组中去

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

row 数组是每次临时新建的

［总结］：

要返回数据结构的，先新建确保类型了再cc

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

arraylist.add即可

［关键模板化代码］：

add两次：

for (int j = 0; j < i + 1; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                }else {
                    row.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
                }     
            }
            //add again
                triangle.add(new ArrayList(row));
        }

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

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

View Code

[代码风格] ：

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

［抄题］：

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

［一句话思路］：

只处理一行即可

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

用get存取改变数组值的时候要用temp暂存

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

额我也不知道j为什么要倒序相加，直接背吧

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

倒序+暂存

for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j >= 1; j--) {//remember reverse
                int tmp = ret.get(j - 1) + ret.get(j);//
                ret.set(j, tmp);
            }

［其他解法］：

［Follow Up］：

做题先看这个，免得答案不一样，费事

［LC给出的题目变变变］：

[代码风格] ：

class Solution {
    public List<Integer> getRow(int rowIndex) {
        //ini
        List<Integer> ret = new ArrayList<Integer>();
        
        //cc
        if (rowIndex <= 0) {
            return ret;
        }
        
        //for
        ret.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j >= 1; j--) {//remember reverse
                int tmp = ret.get(j - 1) + ret.get(j);//
                ret.set(j, tmp);
            }
            ret.add(1);
        }
        
        //return
        return ret;
    }
}

View Code