Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
利用上一行更新下一行
public class Solution { //Time: O(n ^ 2) Space: O(n ^ 2) public ArrayList<ArrayList<Integer>> generate(int numRows) { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if (numRows <= 0) { return res; } ArrayList<Integer> first = new ArrayList<Integer>(); first.add(1); res.add(first); for (int i = 1; i < numRows; i++) { ArrayList<Integer> last = res.get(res.size() - 1); ArrayList<Integer> tmp = new ArrayList<Integer>(); tmp.add(1); for (int j = 0; j < last.size() - 1; j++) { tmp.add(last.get(j) + last.get(j + 1)); } tmp.add(1); res.add(tmp); } return res; } }
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
Could you optimize your algorithm to use only O(k) extra space?
public class Solution { //Time: O(n^2) Space: O(n) public ArrayList<Integer> getRow(int rowIndex) { ArrayList<Integer> res = new ArrayList<Integer>(); if (rowIndex < 0) { return res; } res.add(1); for (int i = 1; i <= rowIndex; i++) { ArrayList<Integer> temp = new ArrayList<Integer>(); temp.add(1); for (int j = 1; j < res.size(); j++) { temp.add(res.get(j) + res.get(j - 1)); } temp.add(1); res = temp; } return res; } }
No comments:
Post a Comment