PascalsTriangleII [source code]

public class PascalsTriangleII {
static
/******************************************************************************/
public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new LinkedList<>();
        if (rowIndex < 0) return row;
        row.add(1);
        if (rowIndex == 0) return row;
        for (int i = 0; i < rowIndex; i++) {
            row.add(0, 1);
            for (int j = 1; j < row.size() - 1; j++) row.set(j, row.get(j) + row.get(j + 1));
        }
        return row;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PascalsTriangleII.Solution tester = new PascalsTriangleII.Solution();
        for (int i = 0; i <= Integer.parseInt(args[0]); i++) System.out.println(tester.getRow(i));
    }
}

仔细读题, 这里的这个 rowIndex 是0-base 的;

题目的总体思路还是很简单的, 就是之前有一个类似的题目里面看来的一个 InPlace 的方法; 最后的速度是3ms (15%). 不过这个代码是完成了 Follow-Up 的;

这个是 submission 最优解1(89):

public class Solution {     
    public List<Integer> getRow(int rowIndex) {  
        Integer[] rowList = new Integer[rowIndex+1];  
        rowList[0] = 1;  
        for(int i=1; i<rowList.length;i++) {  
            rowList[i] = (int) ((long) rowList[i - 1] * (rowIndex - (i - 1)) / (i));  
        }  
        return Arrays.asList(rowList);  
    }      
}

这个好像就是把 list 换成了 array 来做完成的一个加速, 看看就好;
不对, 这个算法好像是有点门道的, 他这里只用一个循环就完成了;

在 discussion 翻到作者了, 这个是解释:

Here is a Java version similar to @guidocelada and @Liuqi.L, which is based on Binomial theorem. Instead of floating operation, I use long integer to handle multiplication overflow. Hope this will be a little faster in some case.

所以是有一个数学上的道理的; 另外注意这个代码里面对于 overflow 的处理(人家一看到加法乘法这种正向的运算立刻就想到处理 overflow 了). 好像其他的这个算法的类似版本别人多数是用 cast 到 floating 来避免 overflow 的;

这个是另外一个解释:
Based on rules:
row k of Pascal's Triangle:
[C(k,0), C(k,1), ..., C(k, k-1), C(k, k)]
and
C[k,i] = C[k,i-1]*(k-(i-1))/i

所以这个还是没有想到的; 稍微注意一点的是这里的这个 k 和 i 都是0-base 的;

Problem Description

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

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

Difficulty:Easy
Total Accepted:116.2K
Total Submissions:318.8K
Contributor: LeetCode
Companies
amazon
Related Topics
array
Similar Questions
Pascal's Triangle