Problem Description:
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?
1 public List<Integer> getRow(int rowIndex) { 2 List<Integer> row = new ArrayList<Integer>(); 3 List<Integer> preRow = new ArrayList<Integer>(); 4 for (int i = 0; i <= rowIndex; i++) { 5 preRow.add(1); 6 row.add(1); 7 } 8 for (int i = 0; i <= rowIndex; i++) { 9 for (int j = 0; j <= i; j++) { 10 if (j == 0 || j == i) { 11 row.set(j, 1); 12 } else { 13 row.set(j, preRow.get(j-1)+preRow.get(j)); 14 } 15 } 16 List<Integer> temp = preRow; 17 preRow = row; 18 row = temp; 19 } 20 21 return preRow; 22 }
Problem Pascal's Triangle II,布布扣,bubuko.com
原文:http://www.cnblogs.com/liew/p/3815134.html