Pascal's Triangle II 解答

Question

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Solution

Similar with Pascal's Triangle. Note that the index starts from 0.

 1 public class Solution {
 2     public List<Integer> getRow(int rowIndex) {
 3         List<Integer> result = new ArrayList<Integer>();
 4         List<Integer> prev = new ArrayList<Integer>();
 5         if (rowIndex < 0)
 6             return result;
 7         result.add(1);
 8         prev.add(1);
 9         while (rowIndex > 0) {
10             result = new ArrayList<Integer>();
11             result.add(1);
12             int length = prev.size();
13             for (int i = 0; i < length - 1; i++)
14                 result.add(prev.get(i) + prev.get(i + 1));
15             result.add(1);
16             prev = result;
17             rowIndex--;
18         }
19         return result;
20     }
21 }

We can also only use one list.

 1 public List<Integer> getRow(int rowIndex) {
 2     ArrayList<Integer> result = new ArrayList<Integer>();
 3  
 4     if (rowIndex < 0)
 5         return result;
 6  
 7     result.add(1);
 8     for (int i = 1; i <= rowIndex; i++) {
 9         for (int j = result.size() - 2; j >= 0; j--) {
10             result.set(j + 1, result.get(j) + result.get(j + 1));
11         }
12         result.add(1);
13     }
14     return result;
15 }