首页 > itarticle > algorithm notes: leetcode#118 pascal’s triangle

algorithm notes: leetcode#118 pascal’s triangle

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

class (object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        result = []
        for r in range(numRows):
            row = [1] * (r+1)
            for c in range(1, r):
                row[c] = result[r-1][c-1] + result[r-1][c]
            result.append(row)
        return result

Java implementation

class  {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for(int r = 0; r < numRows; r++){
            List<Integer> row = new ArrayList<Integer>();
            row.add(1);
            for(int c = 1; c < r; c++){
                row.add(result.get(r-1).get(c-1)+result.get(r-1).get(c));
            }
            if(r>0){ row.add(1); }
            result.add(row);
        }
        return result;
    }
}

Time complexity

O(n²)

Space complexity

O(n²)

Link

118. Pascal’s Triangle
(中文版) 算法笔记: 力扣#118 杨辉三角