【每日一题】4.LeetCode——杨辉三角

简介: 【每日一题】4.LeetCode——杨辉三角


1.题目描述

给定一个非负整数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 <= numRosw <= 30

题目链接🔗

2. 解题思路

杨辉三角的性质:

  1. 三角形的每一行的第一个数字和最后一个数字都是1。
  2. 每一个三角的元素等于上一行此位置左边的元素与上一行此位置元素的和。

题解:

杨辉三角的第0行只有一个数:1。对于 1 ≤ i < numRows。用pervRow表示杨辉三角的第 i - 1行,用curRow表示杨辉三角的第 i 行.

  1. 将 1 添加到curRow,表示当前行的首个数是1
  2. 当前行的中间 i - 1个数分别等于其上方两数之和,因此对于 1 <= j < i,有curRow[j] = pervRow[j] + pervRow[j - 1] ,依次将每个pervRow[j] + pervRow[j - 1]添加到curRow中。
  3. 将 1添加到curRow,表示当前行的末尾数是1.
  4. 此时得到完整的curRow,将curRow添加到杨辉三角。

3. 代码

class Solution {
    public List<List<Integer>> generate(int numRows) {
        // 定义一个二维数组
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(1);
        ret.add(list);
        for (int i = 1; i < numRows; i++) {
            // 每循环一次 就是一行
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1); // 一行的第一个元素
            // 处理中间元素
            List<Integer> pervRow = ret.get(i - 1);
            for (int j = 1; j < i; j++) {
                int x = pervRow.get(j) + pervRow.get(j - 1);
                curRow.add(x);
            }
            //最后一个元素
            curRow.add(1);
            ret.add(curRow);
        }
        return ret;
    }
}

运行结果:

4. 复杂度分析

  • 时间复杂度:O(numRows2),因为计算总数为 1 + 2 + 3 + …+ numRows。
  • 空间复杂度:O(numRows2),因为每次计算都会被保留下来,因此空间复杂度的规模与时间复杂度相同。
相关文章
|
7月前
|
索引
leetcode-119:杨辉三角 II
leetcode-119:杨辉三角 II
61 0
|
6月前
|
存储 SQL 算法
LeetCode 题目 118:杨辉三角
LeetCode 题目 118:杨辉三角
|
7月前
leetcode代码记录(杨辉三角
leetcode代码记录(杨辉三角
41 1
|
7月前
leetcode-118:杨辉三角
leetcode-118:杨辉三角
58 0
|
算法
【LeetCode】136. 只出现一次的数字、118. 杨辉三角
目录 136. 只出现一次的数字 118. 杨辉三角
51 0
leetcode:118. 杨辉三角
函数原型:int** generate(int numRows, int* returnSize, int** returnColumnSizes) 参数解析:numRows是指明要求前几行杨辉三角 returnSize是返回指针数组的元素个数 returnColumnSizes是指明杨辉三角每一行有几个元素
68 0
力扣118.杨辉三角
给定一个非负整数 numRows生成「杨辉三角」的前 numRows行。在「杨辉三角」中,每个数是它左上方和右上方的数的和。链接位置:力扣。
47 0
|
算法
《LeetCode-数组篇一》之杨辉三角与重塑矩阵
《LeetCode-数组篇一》之杨辉三角与重塑矩阵
119 0
|
存储
力扣119杨辉三角 II:代码实现 + 方法总结(数学规律法 & 记忆法/备忘录)
力扣119杨辉三角 II:代码实现 + 方法总结(数学规律法 & 记忆法/备忘录)
94 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行