[LeetCode]--119. Pascal's Triangle II

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?

public List<Integer> getRow(int rowIndex) { List<Integer> list = new ArrayList<Integer>(); List<List<Integer>> resultList = new ArrayList<List<Integer>>(); int[][] temp = new int[rowIndex + 1][rowIndex + 1]; for (int i = 0; i < rowIndex + 1; i++) { temp[i][0] = 1; temp[i][i] = 1; for (int j = 0; j <= i; j++) { if (j < i && i > 1 && j > 0) temp[i][j] = temp[i - 1][j - 1] + temp[i - 1][j]; list.add(temp[i][j]); } resultList.add(list); list = new ArrayList<Integer>(); } return resultList.get(rowIndex); }

我开辟了两倍的空间，因为有一半没用山，这种也通过了，后来想着用一倍空间也能完成。

public List<Integer> getRow(int rowIndex) { List<Integer> list = new ArrayList<Integer>(); rowIndex++; list.add(1); for (int i = 1; i < rowIndex; i++) { List<Integer> temp = new ArrayList<Integer>(i + 1); //这里记住了，一定要进行初始化，然后set会出错 for (int j = 0; j < i + 1; j++) temp.add(-1); temp.set(0, list.get(0)); temp.set(i, list.get(i - 1)); for (int j = 1; j < i; j++) temp.set(j, list.get(j - 1) + list.get(j)); list = temp; } return list; }