Wednesday, April 8, 2015

LeetCode [118] Pascal's Triangle

 118. Pascal's Triangle

Easy

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]
]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret;
        for(int i=1; i<=numRows; ++i){
            vector<int> row(i);
            for(int j=1; j<=i; ++j){
                if(j==1 || j==i) row[j-1] = 1;
                else row[j-1] = ret.back()[j-2]+ret.back()[j-1];
            }
            ret.push_back(row);
        }
        return ret;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();
        for(int i=0; i<numRows; ++i){
            List<Integer> list = new ArrayList<>();
            list.add(1);
            for(int j=1; j<i; ++j){
                list.add(lists.get(i-1).get(j-1)+lists.get(i-1).get(j));
            }
            if(i>0) list.add(1);
            lists.add(list);
        }
        return lists;
    }
}

No comments:

Post a Comment