118. Pascal's Triangle

Question:

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Thinking:

• Method:
  • 使用递归，每一个结果是由上一层的结果决定的。
  • 0， 1， 2需要特殊处理。
  • 下一层需要填充的位置的值：a[i] = last[i - 1] + last[i];

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        if(numRows == 0) return result;
        List<Integer> temp = new ArrayList<>();
        temp.add(1);
        result.add(temp);
        if(numRows == 1){
            return result;
        }else{
            generate(numRows, result);
        }
        return result;
    }
    private static void generate(int n, List<List<Integer>> result){
        if(n == 2){
            List<Integer> temp = new ArrayList<>();
            temp.add(1);
            temp.add(1);
            result.add(temp);
        }else{
            generate(n - 1, result);
            List<Integer> last = result.get(n - 2);
            List<Integer> add = new ArrayList<>();
            add.add(1);
            for(int i = 1; i < n - 1; i++){
                add.add(last.get(i - 1) + last.get(i));
            }
            add.add(1);
            result.add(add);
        }
    }
}

二刷

要注意一下Arrays.asList方法，没有自动装箱功能。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new LinkedList<>();
        if(numRows == 0) return result;
        generate(result, numRows);
        return result;
    }
    private void generate(List<List<Integer>> result, int index){
        if(index == 1){
            result.add(Arrays.asList(1));
        }else if(index == 2){
            generate(result, index - 1);
            result.add(Arrays.asList(1, 1));
        }else{
            generate(result, index - 1);
            List<Integer> last = result.get(result.size() - 1);
            Integer[] current = new Integer[index];
            current[0] = 1; current[index - 1] = 1;
            for(int i = 1; i < index - 1; i++){
                current[i] = last.get(i) + last.get(i - 1);
            }
            result.add(Arrays.asList(current));
        }
    }
}