leetcode — pascals-triangle-ii

import java.util.Arrays;

/**

 *

 * Source : https://oj.leetcode.com/problems/pascals-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?

 *

 */

public class PascalTriangle2 {

    /**

     * 获取杨辉三角的第n行

     * 占用常数空间，使用长度为n的数组，依次计算 ...i-2,i-2,i 行的数据，可以根据俄第i-1行的结果来计算i行，

     * 计算每行数据的时候，如果从前向后填入的话，会把后面的覆盖就不能继续计算，那么就从后向前

     *

     * @param n

     * @return

     */

    public int[] getRow (int n) {

        int[] row = new int[n];

        row[0] = 1;

        if (n == 1) {

            return row;

        }

        for (int i = 2; i <= n; i++) {

            for (int j = i; j > 1; j--) {

                row[j-1] = row[j-1] + row[j-2];

            }

        }

        return row;

    }

    public static void main(String[] args) {

        PascalTriangle2 pascalTriangle2 = new PascalTriangle2();

        System.out.println(Arrays.toString(pascalTriangle2.getRow(5)));

    }

}
巴特西

leetcode — pascals-triangle-ii

最新文章

热门文章
