LeetCode-119 杨辉三角Ⅱ

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例

示例一

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

示例二

输入: rowIndex = 0
输出: [1]

示例三

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

方法一 通过杨辉三角的结果得到最后一行数据

杨辉三角解析详情：LeetCode-119 杨辉三角Ⅱ

class Solution {public List<Integer> getRow(int rowIndex) {List<List<Integer>> result = new ArrayList<List<Integer>>();for(int i = 0; i <= rowIndex; i++){List<Integer> iCurrnt = new ArrayList<Integer>();for(int j = 0; j <=i; j++){if(j==0 || j == i){iCurrnt.add(1);continue;}iCurrnt.add(result.get(i-1).get(j) + result.get(i-1).get(j-1));}result.add(iCurrnt);}return result.get(rowIndex);}
}

方法二、动态规划

解析

由题目可知，杨辉三角的第i行的元素个数为i+1，且两侧都是1
我们定义一个元素值全为1的数组dp，我们可以在dp上一步步的算出所求数组

for(int i = 2;i < dp.length;i++){for(int j = i - 1;j > 0;j--){dp[j] = dp[j] + dp[j - 1];}}

我们从rowIndex=2开始计算，因为当rowIndex=1或者rowIndex=0是，数组中的元素全为1.
用杨辉三角可得，其所组成为二维数组为下三角形，因此，当i==j时，元素也是1
因此从j == i -1来计算
此时dp中元素值全为1，根据计算公式可以得到第三行
随后不断在上一步计算出的数组加工

class Solution {public List<Integer> getRow(int rowIndex) {Integer[] result = new Integer[rowIndex + 1];Arrays.fill(result,1);for(int i = 2; i<result.length; i++){for(int j = i -1; j>0;j--){result[j] = result[j] + result[j - 1];}}List<Integer> res = Arrays.asList(result);return res;}
}

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