【LC简单】118. 杨辉三角

简介: 【LC简单】118. 杨辉三角

题目描述:

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

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

73d8c9be8b2a4960a39693770de0ac9a.png

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

提交结果:73d8c9be8b2a4960a39693770de0ac9a.png

目录
相关文章
|
7月前
【每日一题Day202】LC1015可被 K 整除的最小整数 | 模运算
【每日一题Day202】LC1015可被 K 整除的最小整数 | 模运算
67 2
|
7月前
【每日一题Day366】LC2103环和杆 | 状态压缩
【每日一题Day366】LC2103环和杆 | 状态压缩
49 0
|
7月前
【每日一题Day290】LC1281整数的各位积和之差 | 模拟
【每日一题Day290】LC1281整数的各位积和之差 | 模拟
44 0
|
7月前
【每日一题Day268】LC415字符串相加 | 模拟
【每日一题Day268】LC415字符串相加 | 模拟
48 0
|
7月前
【每日一题Day185】LC1027最长等差数列 | dp
【每日一题Day185】LC1027最长等差数列 | dp
47 0
|
7月前
|
存储
【每日一题Day253】LC2两数相加 | 链表模拟
【每日一题Day253】LC2两数相加 | 链表模拟
25 0
|
7月前
【每日一题Day242】LC1262可被三整除的最大和 | 贪心 dp
【每日一题Day242】LC1262可被三整除的最大和 | 贪心 dp
51 0
|
7月前
【每日一题Day194】LC970强整数 | 枚举
【每日一题Day194】LC970强整数 | 枚举
38 0
|
6月前
|
PHP C++
LC59螺旋矩阵II
LC59螺旋矩阵II
27 0
|
7月前
【每日一题Day256】LC2600K 件物品的最大和
【每日一题Day256】LC2600K 件物品的最大和
48 2