PascalsTriangleOPT2 [source code]

public class PascalsTriangleOPT2 {
static
/******************************************************************************/
public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> allrows = new ArrayList<List<Integer>>();
        ArrayList<Integer> row = new ArrayList<Integer>();
        for (int i = 0; i < numRows; i++) {
            row.add(0, 1);
            for (int j = 1; j < row.size() - 1; j++) row.set(j, row.get(j) + row.get(j + 1));
            allrows.add(new ArrayList<Integer>(row));
        }
        return allrows;        
    }
}
/******************************************************************************/

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

这个算法是 discussion 上面的一个最优解, 实际上的速度跟我的算法是一样的, 而且空间占用也是一样的, 就是加了一些小技巧而已;

注意这里 allrows.add(new ArrayList<Integer>(row)) 不能直接写成allrows.add(row), 因为最后得到的 triangle 虽然还是有那么多的 row, 但是所有的 row 都是一样的, 因为他们其实都是指向同一个(最后一个) row 的相同的指针;

这个是 comment 里面一个人的解释:
The reason is that: row is an object. If we just do allrows.add(row); and this row object is changed in future operations, it will affect and changed what it is in our allrows. So we need to copy it, create a new object, and then save it to allrows.

这个算法虽然完成了一个我当时设计自己的算法的时候想要完成的一个目标, 就是不需要额外维护前一排, 完成一个in place update, 但是最后实际上空间占用还是一样的.
尽管如此, 这个 InPlace 的完成还是值得学习的;
不过这里他这个InPlace 的技巧的完成方式并不具有普遍的学习意义, 就是针对这个问题的特性而已: 他把边缘和内部分开处理;
这样处理还有一个好处就是, 不需要进行边界检查了;

这里还有一个隐藏的小处理: 他的加法是[i] + [i + 1], 而不是[i] + [i - 1], 这个也是能够完成 InPlace 的一个关键, 因为如果你在 Access 的时候还要回头看, 也就是看前面已经被更新过一次的[i - 1], 你就没有办法用一个 pass 的 stream 直接做完这个更新;

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