LeetCode-118. 杨辉三角I(java)

bug菌

发布于 2023-05-27 15:16:36

4980

文章被收录于专栏：《项目实战教学》《项目实战教学》

一、前言：

👨‍🎓作者：bug菌 ✏️博客：CSDN、掘金等 💌公众号：猿圈奇妙屋 🚫特别声明：原创不易，转载请附上原文出处链接和本文声明，谢谢配合。 🙏版权声明：文章里可能部分文字或者图片来源于互联网或者百度百科，如有侵权请联系bug菌处理。

二、题目描述：

题目：

给定一个非负整数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官网题目难度：⭐⭐

三、思路分析：

这题就很经典啦，曾记否大学java课本上就有讲解这道题，当时还布置这题的变种题给我们作为课后作业，如上题就是等边形状杨辉三角，还有一种就是直角形状杨辉三角。根据如上动画找规律，传统解法就是根据规律来解题。

每一行的开始和结尾数字都为1。
第n+1行的第i个数字等于第n行的i-1个数字加上第 n 行的i个数字。用二维数组表示就是 a[i+1][j]=a[i][j-1]+a[i][j]

根据上述两点规律，已经给你分析的明明白白，你难道还会解不出这道题么，你只需要根据我上方梳理的两点规律书写成代码即可。

四、算法实现：

AC代码

具体算法代码实现如下：

class Solution {
     public List<List<Integer>> generate(int numRows) {
  
         //定义一个二维集合。
         List<List<Integer>> ret = new ArrayList<List<Integer>>();
         for (int i = 0; i < numRows; i++) {
             //内置集合
             List<Integer> row = new ArrayList<Integer>();
             //由于只是给杨辉三角内的位置赋值，所以是j<=i
             for (int j = 0; j <= i; j++) {
                 //根据规律，使用if else 赋值
                 //头尾都是1
                 if (j == 0 || j == i) {
                     row.add(1);
                 } else {
                     row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                 }
             }
             ret.add(row);
         }
         return ret;
     }
 }