问题描述
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 { public List > generate(int numRows) { List > res = new ArrayList >(); if (numRows <= 0) { return res; } List list = new ArrayList (); list.add(1); res.add(list); if (numRows == 1) { return res; } list = new ArrayList (); list.add(1); list.add(1); res.add(list); if (numRows == 2) { return res; } for (int i = 2; i < numRows; i++) { List tmp = res.get(i - 1); List add = new ArrayList (); add.add(1); for (int j = 0; j < i - 1; j++) { add.add(tmp.get(j) + tmp.get(j + 1)); } add.add(1); res.add(add); } return res; }}
Follow up
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return[1,3,3,1]. Note:
Could you optimize your algorithm to use only O(k) extra space?
解决思路
辅助的中间list存上一个list的结果。交替进行。
程序
public class Solution { public List getRow(int rowIndex) { List row = new ArrayList (); if (rowIndex < 0) { return row; } row.add(1); if (rowIndex == 0) { return row; } row.add(1); if (rowIndex == 1) { return row; } List tmp = new ArrayList (row); int i = 2; while (i <= rowIndex) { int mids = i - 1; row = new ArrayList (); row.add(1); for (int j = 0; j < mids; j++) { row.add(tmp.get(j) + tmp.get(j + 1)); } row.add(1); tmp = new ArrayList (row); ++i; } return row; }}