118. Pascal's Triangle.md

118. Pascal's Triangle

---

leetcode-cn Daily Challenge on December 6th, 2020.

---

Difficulty : Easy

Related Topics : Array

---

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
    [1],
   [1,1],
  [1,2,1],
 [1,3,3,1],
[1,4,6,4,1]
]

---

Solution

• mine
  • Java
    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.2 MB, less than 64.47% of Java online submissions

      // O(K^2)time
      // O(K^2)space
      public List<List<Integer>> generate(int numRows) {
          List<List<Integer>> res = new ArrayList<>();
          while (numRows > 0) {
              numRows--;
              List<Integer> t = new ArrayList<>();
              t.add(1);
              if (res.size() > 0) {
                  List<Integer> pre = res.get(res.size() - 1);
                  if (pre.size() == 1) {
                      t.add(1);
                  } else {
                      for (int i = 1; i < pre.size(); i++) {
                          t.add(pre.get(i - 1) + pre.get(i));
                      }
                      t.add(1);
                  }
              }
              res.add(t);
          }
          return res;
      }
      

---