题目描述:
给定一个非负整数 numRows,生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
1 <= numRows <= 30
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/pascals-triangle
解题思路:
观察题目给出方法返回值为List<List>和给出的示例; 题目的要求是返回一个线性表, 线性表中的每个元素为杨辉三角的每一行 , 也就是说返回的线性表表中的每个元素其实也是一个线性表 , 这里线性表中的每个元素为一个int类型的值 , 题目可以选择用顺序表去实现 ;
观察杨辉三角的规律 , 其第一行只有一个数字1, 先将其添加到一个顺序表中 , 再将这个顺序表添加到要返回的顺序表中 ; 从第二行开始就要找找规律了, 其每一行的第一个数字和最后一个数字都为1, 中间的数字为上一行顺序表中相同位置元素和前一个位置元素的和 , 这里,可以利用一个嵌套循环实现 , 每次循环先将第一个元素1添加到顺序表中, 内层循环实现将中间的数字添加到顺序表中, 再将最后一个元素1添加到顺序表中 , 最后将这个代表一行的顺序表添加到要返回的顺序表中;
至于获取中间的每个数字 , 只需要去访问要返回的顺序表中上一行对应两个位置的元素 , 求和即可 .
代码实现:
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> ret = new ArrayList<>(); //第一行 List<Integer> list1 = new ArrayList<>(); //第一行只有一个数字1 list1.add(1); ret.add(list1); //再从第二行计算 for(int i = 1; i < numRows; i++) { //当前行 List<Integer> list = new ArrayList<>(); //每一行的第一个数字都为1 list.add(1); //获取上一行 List<Integer> prevRow = ret.get(i-1); //从第二行的第一个数字开始计算 for(int j = 1; j < i; j++) { int num = prevRow.get(j)+prevRow.get(j-1); list.add(num); } //每一行的最后一个数字也为1 list.add(1); ret.add(list); } return ret; } }