Pascal's Triangle II

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?

这道题倒是不难，有个有意思的地方是可以优化到O(k)的空间复杂度。下面先上O(k^2)的算法。

    @Test

    public List<Integer> getRow(int rowIndex) {

        int[][] f = new int[rowIndex + 1][rowIndex + 1];

        List<Integer> res = new ArrayList<>();

        for (int i = 0; i <= rowIndex; i++) {

            res.add(getNum(rowIndex, i, f));

        }

        return res;

    }

    public int getNum(int row, int col, int[][] f) {

        if (row == 0 || row == 1 || col == 0 || col == row)

            return 1;

        if (col < 0)

            return 0;

        if (f[row][col] == 0)

            f[row][col] = getNum(row - 1, col, f) + getNum(row - 1, col - 1, f);

        return f[row][col];

    }

上面算法还算比较直观，就是依次取出第rowIndex行的各个元素，加入到list中。通过代码可以发现，第K行的数据仅仅依赖于第K-1行，也就是说，我们可以进行降维，将二维数组降为一维，这里注意，降维之后，用一维数组来记录当前行的数据，计算的时候应从后往前计算，还是以二维进行假设，当前元素为

　　F[k][col]=F[k-1][col]+F[k-1][col-1]

那么，当循环走完k-1遍时，一维数组里的数据F[col]里存的是对应二维数组的F[k-1][col]，从后往前计算，F[col]=F[col]+F[col-1]，那么走完这一遍，F数组里存的是F[k][0...col]的数据，如果从前往后计算，F[col]=F[col]+F[col-1]，仔细看，F[col+1]=F[col+1]+F[col]，这里就有问题了，F[col]这里已经不是k-1状态的数据了，所以这样计算有问题。这个降维的技巧在动态规划里也经常用，注意要从后往前计算。

Talk is cheap。

　　public ArrayList<Integer> getRow(int rowIndex) {

        ArrayList<Integer> res = new ArrayList<>();

        if (rowIndex < 0)

            return res;

        res.add(1);

        for (int i = 1; i <= rowIndex; i++) {

            for (int j = res.size() - 2; j >= 0; j--) {

                res.set(j + 1, res.get(j) + res.get(j + 1));

            }

            res.add(1);

        }

        return res;

    }

巴特西

Pascal's Triangle II —LeetCode

最新文章

热门文章