PascalsTriangleOPT [source code]

public class PascalsTriangleOPT {
static
/******************************************************************************/
public class Solution {
    public List<List<Integer>> generate(int numRows) {
        int result[][] = new int[numRows][];
        // corner case
        if (numRows == 0) {
            return new ArrayList<>();
        }
        // first row
        result[0] = new int[1];
        result[0][0] = 1;

        for (int i = 1; i < numRows; i++) {
            result[i] = new int[i + 1];
            result[i][0] = 1;
            for (int j = 1; j < i; j++) {
                result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
            }
            result[i][i] = 1;
        }

        List arrayList = Arrays.asList(result);
        return arrayList;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PascalsTriangleOPT.Solution tester = new PascalsTriangleOPT.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();
        }
    }
}

这个算法是 submission 最优解, 0ms. 实际上也没有什么神奇的地方, 就是拿空间换时间. 用 array 来让存取速度更快的想法我刚开始也是想到了的, 就是感觉这个 array 反正还是每一个 row 的时候都要更新一次, 显得有点没有意义, 就没有做了, 不过他这个空间占用好像是可以优化下来的;

跟我当时想法稍微有点区别的地方在于, 我当时认为只要做一个一维的 array, 来保存上一个row 就行了, 他这里是整个 triangle 全部都用一个二维的 array 来做, 唯一出现 list 的地方就是最后的返回的时候转化一下就行了;

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