Question

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

Thinking:

  • Method 1:BFS
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>();
        getRow(rowIndex, list);
        return list;
    }
    private static void getRow(int rowIndex, List<Integer> list){
        if(rowIndex == 0){
            list.add(1);
        }else if(rowIndex == 1){
            list.add(1);
            list.add(1);
        }else{
            getRow(rowIndex - 1, list);
            int len = list.size();
            LinkedList<Integer> temp = new LinkedList<>();
            for(int i = 0; i < len - 1; i++){
                temp.add(list.get(i) + list.get(i + 1));
            }
            list.clear();
            list.add(1);
            list.addAll(temp);
            list.add(1);
        }
    }
}

二刷

和一刷的思路一样，还是递归。但是看了一下别人的答案，因为每行的数字个数是确定的，所以我们只需要用数组就可以了。

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new LinkedList<>();
        getRow(result, rowIndex);
        return result;
    }
    private void getRow(List<Integer> list, int index){
        if(index == 0) list.add(1);
        else if(index == 1){
            Integer[] arr = {1, 1};
            list.addAll(Arrays.asList(arr));
        }else{
            getRow(list, index - 1);
            Integer[] res = new Integer[index + 1];
            res[0] = 1; res[index] = 1;
            for(int i = 1; i < index; i++){
                res[i] = list.get(i) + list.get(i - 1);
            }
            list.clear();
            list.addAll(Arrays.asList(res));
        }
    }
}