PascalsTriangle [source code]

public class PascalsTriangle {
static
/******************************************************************************/
public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new LinkedList<>();
        if (numRows <= 0) return res;
        List<Integer> level = new LinkedList<>();
        level.add(1);
        res.add(level);
        if (numRows == 1) return res;
        for (int i = 2; i <= numRows; i++) {
            List<Integer> thisLevel = new LinkedList<>();
            for (int j = 0; j < i; j++) {
                int operand1 = j - 1 >= 0 ? level.get(j - 1) : 0;
                int operand2 = j >= i - 1 ? 0 : level.get(j);
                thisLevel.add(operand1 + operand2);
            }
            res.add(thisLevel);
            level = thisLevel;
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PascalsTriangle.Solution tester = new PascalsTriangle.Solution();
        int N = Integer.parseInt(args[0]);
        List<List<Integer>> triangle = tester.generate(N);
        for (List<Integer> ls : triangle) {
            for (int i : ls) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}

这个问题总体来说还是很简单的, 但是我想代码的时候一直想着能不能够做到直接一套代码把包含前两行的计算也包含进去, 这样就避免对于 Corner Case 的判断太多: 但是这个就属于 premature optimization 了; 这个是我目前的一大 trap;

这题稍微有两个难点就是要把三角形用左边对其的方式来计算;
然后就是边界的判断和处理;

其他的基本就是一个空间和时间上的优化, 本身逻辑很简单, 最后的速度是1ms (28%), 还算 ok;

Problem Description

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Difficulty:Easy
Category:Algorithms
Acceptance:38.16%
Contributor: LeetCode
Companies
apple twitter
Related Topics
array
Similar Questions
Pascal's Triangle II