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