leetCode-119: 杨辉三角 II

与 118.杨辉三角_jiaomubai的博客-CSDN博客 这篇文章不同的是，杨辉三角 II 要求输出第 n 行的数据，不在输出前 n 行的值。

示例：

输入: rowIndex = 3
输出: [1,3,3,1]

返回第 n 行的杨辉三角值比返回前 n 行的杨辉三角值更适合使用递归来求解，所以此题与 70.爬楼梯_jiaomubai的博客-CSDN博客 类似，我们仍采用多种方法进行求解。

根据示例，我们可以看到，实际输出的杨辉三角值其实是输入值 + 1 行的杨辉三角值。在代码中我们使用到了杨辉三角的一个非常重要的公式：第 n 行的第 m 个数可表示为 C(n-1，m-1)，即为从 n - 1 个不同元素中取 m - 1 个元素的组合数。

相关代码如下：

public class GetRow {// 递归public static List getRow(int rowIndex) {Integer[] array = new Integer[rowIndex + 1];// rowIndex = 0 时，直接返回 [1]if (rowIndex == 0) {array[0] = 1;return Arrays.asList(array);}// rowIndex = 1 时，直接返回 [1, 1]if (rowIndex == 1) {array[0] = 1;array[1] = 1;return Arrays.asList(array);}array[0] = 1;array[1] = 1;// 从第三行(即 i = 2)开始使用公式去递归for (int i = 2; i <= rowIndex; i++) {if (i == rowIndex) {array[rowIndex] = 1;}array[i - 1] = getRow(rowIndex - 1).get(i - 2) + getRow(rowIndex - 1).get(i - 1);}return Arrays.asList(array);}// 使用公式迭代// 第 n 行的第 m 个数可表示为 C(n-1，m-1)，即为从 n - 1 个不同元素中取 m - 1 个元素的组合数。public static List getRow2(int rowIndex) {List resultList = new ArrayList<>(rowIndex + 1);resultList.add(1);BigDecimal factorialN = getFactorial(rowIndex);for (int i = 1; i <= rowIndex; i++) {BigDecimal factorialM = getFactorial(i);BigDecimal factorialNM = getFactorial(rowIndex - i);BigDecimal result = factorialN.divide(factorialM.multiply(factorialNM), 4, BigDecimal.ROUND_HALF_UP);resultList.add(result.intValue());}return resultList;}public static BigDecimal getFactorial(int n) {BigDecimal factorial = BigDecimal.ONE;for (int i = 1; i <= n; i++) {factorial = factorial.multiply(new BigDecimal(i));}return factorial;}// 动态规划,第 i 行第 j 个数 = 第 i - 1 行第 j 个数 + 第 i - 1 行第 j - 1 个数public static List getRow3(int rowIndex) {Integer[] dp = new Integer[rowIndex + 1];Arrays.fill(dp,1);// i 控制当前行,i = 2 其实表示的是第三行for(int i = 2; i <= rowIndex; i++) {// j 控制前一行,j = 1 时表示第二个数for (int j = i - 1; j > 0; j--) {dp[j] = dp[j] + dp[j - 1];}}List res = Arrays.asList(dp);return res;}public static void main(String[] args) {long startTime = System.currentTimeMillis();List resultList = getRow3(33);System.out.println(resultList);long endTime = System.currentTimeMillis();System.out.println("程序运行时间：" + (endTime - startTime) + "ms");}}

需要注意的是 getRow2() 方法，刚开始时使用的 Integer，后来发现会越界，又改使用 Long，还是会越界，然后又使用 BigDecimal 才通过全部测试用例，即输出 n = 33 时的杨辉三角值，测试了一下发现如果要输出第 34 行的杨辉三角值的话，以上这几种方法都会越界。当时用 getRow() 方法时，大概计算 getRow(10) 时就会超时。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！