[LeetCode 118] Pascal's Triangle

문제 바로가기

Description

---

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1

---

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

Example 2

---

• Input: numRows = 1
• Output: [[1]]

Constraints

---

• 1 <= numRows <= 30

Code

---

내 제출

---

class Solution {
    public List<List<Integer>> generate(int numRows) {
int[][] triangle = new int[numRows][numRows];
List<List<Integer>> result = new ArrayList<>();

for (int i = 0; i < numRows; i++) {
    triangle[i][0] = 1;
    triangle[i][i] = 1;
    for (int j = 1; j < i; j++) {
        triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
    }
}

for (int i = 0; i < numRows; i++) {
    List<Integer> row = new ArrayList<>();
    for (int j = 0; j < triangle.length; j++) {

        if (triangle[i][j] != 0) {
            row.add(triangle[i][j]);
        } else {
            break;
        }
    }
    result.add(row);
}

return result;
    }
}

Runtime	Memory
1 ms	42.3 MB

다른 풀이

---

class Solution {
    public List<Integer> calculateNCR(int row){
        List<Integer> list =new ArrayList<>();
        list.add(1);
        int res=1;
        for(int i=1;i<row;i++){
            res=res*(row-i);
            res=res/i;
            list.add(res);
        }
        return list;
    }
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list=new ArrayList<>();
        for(int i=1;i<=numRows;i++){
            list.add(calculateNCR(i));
        }
        return list;
    }
}

Reference

---