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;
    }
}
           

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

原文地址：https://blog.csdn.net/kkksij/article/details/142406456

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！