java之杨辉三角问题

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

如何实现呢？

思路：首先，我们可以将杨辉三角视作i行j列的二维数组。除了第一行和第二行之外，其他行的元素都是首尾元素为1且该行的其他元素都是上一行相邻元素之和。有了这个思路，下面的实现步骤就可以有效的进行了。

步骤：

1.创建一个二维列表ret，用来存储每一行的元素。

2.创建一个只有元素1的列表（作为第一行）并将其添加到数组ret中

3.生成后续行：

(1):从第二行开始，通过for循环求该行的每一个元素，直到最后一行:

       for (int i = 1; i < numRows; i++)

(2):通过创建整形列表curRow，创建当前行的列表，同时通过add函数添加该行的第一个元素1。

(3):创建一个整形列表preRow用来接收上一行的值。

4.创建当前行中间的值:

(1):从第二个元素for循环到当前倒数第二个元素。for (int j = 1; j < i; j++) （因为第一个元素和倒数第二个元素都是1.)

(2):设置两个整形int val1 和 int val2，获取上一行相邻的两个元素（ int val1=preRow.get(j); 

         和 int val2 = preRow.get(j-1);） 

(3):将两个值相加后添加到当前行：curRow.add(val1 + val2);

5.添加当前行的最后一个元素1：curRow.add(1)

6.将当前行添加到二维列表ret中。（ret.add(curRow);）

7.返回结果：return ret ，返回生成的杨辉三角。

具体实现代码如下：

class Solution {public List<List<Integer>> generate(int numRows) {List <List<Integer>> ret = new ArrayList<>(); //创建一个二维列表List<Integer> list0 = new ArrayList<>(); // 创建杨辉三角的第一行list0.add(1); //添加杨辉三角的第一个元素ret.add(list0); //将list0添加到ret中//从第二行开始求每个元素for(int i=1;i<numRows;i++){//处理第一个元素List<Integer> curRow = new ArrayList<>();curRow.add(1);//中间List<Integer> preRow = ret.get(i-1); //获取上一行的数组for(int j = 1;j<i;j++){int val1 = preRow.get(j);int val2 = preRow.get(j-1);curRow.add(val1+val2);}//尾巴处添加curRow.add(1);ret.add(curRow);}return ret;}
}

今天的分享就到这，喜欢的老铁来个三连吧