118 Pascal's Triangle

思路

把三角分为三种情况, 第一个1是每一行都有的, 结尾的1是从第二行才开始有, 然后中间的数字是从第三行开始, 对于i位置的数字是他前一行的i位置和i-1位置数字的和

复杂度

时间O(n^2) 空间O(n^2)

代码

public class Solution {    public List
    
     
      > generate(int numRows) {        List
      
       
        > res = new ArrayList<>();        if (numRows<=0) {return res;}        for (int i = 0; i 
        
          tmp = new ArrayList<>();            tmp.add(1); //每一行的第一个数字            for (int j = 1; j< i; j++) {//从第三行开始加入中间的数字                tmp.add(res.get(i-1).get(j) + res.get(i-1).get(j-1));            }            if (i > 0) {//每行最后一个数字                tmp.add(1);            }            res.add(tmp);        }        return res;    }}
        
       
      
     
    

119. Pascal's Triangle II

思路 (迭代相加法)

与1相同, 用另外一个数组来记录上此次遍历的结果

复杂度

时间O(n^2) 空间O(k)

代码

class Solution {    public List
    
      getRow(int rowIndex) {        List
     
       res = new ArrayList<>();        if (rowIndex<0) {return res;}        for (int i = 0; i <=rowIndex; i++) {            List
      
        list = new ArrayList<>();            list.add(1); //每一行的第一个数字            for (int j = 1; j< i; j++) {//从第三行开始加入中间的数字                list.add(res.get(j) + res.get(j-1));            }            if (i > 0) {//每行最后一个数字                list.add(1);            }            res = list;        }        return res;    }}
      
     
    

思路(逆序相加法)

与迭代法相同, 但是我们在同一个list上面操作, 每次从后往前更改list上面的数字. 这样可以节省空间因为只用到一个list

复杂度

时间O(n^2) 空间O(k)

代码

class Solution {    public List
    
      getRow(int rowIndex) {        List
     
       res = new ArrayList<>();        if (rowIndex<0) {return res;}        res.add(1);        for (int i = 0; i 
      
       0; j--) {               res.set(j, res.get(j) + res.get(j-1));           }            res.add(1);        }        return res;    }}