dp--118.杨辉三角/easy 理解度A

118.杨辉三角

  • 1、题目
  • 2、题目分析
  • 3、解题步骤
  • 4、复杂度最优解代码示例
  • 5、抽象与扩展

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 <= numRows <= 30
Related Topics
  • 数组
  • 动态规划

2、题目分析

1、每层的首、尾 2 个位置,直接设置为 1
2、每层除了首、尾,本层j位置的值 = 上层j-1位置的值 + 上层j位置的值

3、解题步骤

1、循环生成杨辉三角的层数
2、处理指定层数(i层)的数据
2.1、每层的首、尾 2 个位置,直接设置为 1
2.2、每层除了首、尾,本层j位置的值 = 上层j-1位置的值 + 上层j位置的值
3、将本层结果存入杨辉三角

4、复杂度最优解代码示例

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            // 1、循环生成杨辉三角的层数
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                // 2、处理指定层数(i层)的数据
                if (j == 0 || j == i) {
                    // 2.1、每层的首、尾 2 个位置,直接设置为 1
                    row.add(1);
                    continue;
                }
                // 2.2、每层除了首、尾,本层j位置的值 = 上层j-1位置的值 + 上层j位置的值
                List<Integer> upperLevels = res.get(i - 1);
                row.add(upperLevels.get(j - 1) + upperLevels.get(j));
            }
            // 3、将本层结果存入杨辉三角
            res.add(row);
        }
        return res;
    }

5、抽象与扩展

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/299596.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Spring+Vue实战项目环境准备跑通程序

SpringVue 源项目 后端&#xff1a; 首先在GitHub上克隆项目到本地&#xff08;zip包下载/sourcetree拉取/gitbash克隆&#xff09;。 https://github.com/songboriceman/doubao_community_backend 然后下载Lombok安装到你的IDE&#xff08;eclipse&#xff09;。 https://p…

如何将手机中termux用电脑的vnc显示

在电脑中我们同样需要下载 vnc 这里填写手机上的 IP&#xff1a;端口号 我的是 10.11.166.219:5902 下面填名字然后 手机端 输入sshd开始ssh这边就可以连接啦

跨平台开发教学:构建同时支持iOS和Android的教育网校APP

当下&#xff0c;教育行业也逐渐迎来了数字化转型的时代。构建一款支持iOS和Android的教育网校APP&#xff0c;不仅可以提供更好的用户体验&#xff0c;还能扩大应用的覆盖面&#xff0c;满足不同用户群体的需求。 一、选择合适的跨平台开发框架 在开始构建教育网校APP之前&a…

14_IO_其他流

文章目录 数据流DataOutputStream数据输出流DataInputStream数据输入流 打印流PrintStream字节打印流PrintWriter字符打印流 标准输入输出流标准输入流标准输出流 对象流(序列化与反序列化流)ObjectOutputStream序列化流ObjectInputStream反序列化流 RandomAccessFile随机访问文…

八大算法排序@快速排序、递归版本一(C语言版本)

目录 快速排序版本一概念算法思想一二三 快排步骤代码实现时间复杂度空间复杂度特性总结 快速排序版本一 概念 快速排序&#xff08;Quicksort&#xff09;是一种高效的排序算法&#xff0c;它是由英国计算机科学家 Tony Hoare 在1960年提出的。快速排序是基于分治&#xff08…

STM32深入系列02——BootLoader分析与实现

文章目录 1. STM32程序升级方法1.1 ST-Link / J-link下载1.2 ISP&#xff08;In System Programing&#xff09;1.3 IAP&#xff08;In Applicating Programing&#xff09;1.3.1 正常程序运行流程1.3.2 有IAP时程序运行流程 2. STM32 Bootloader实现2.1 方式一&#xff1a;Boo…

西电期末1026.删除特定字符后排序输出

一.题目 二.分析与思路 题目名字很有意思&#xff0c;先删除后排序&#xff0c;难死了&#xff0c;还是先排序后删除简单吧&#xff1f;注意字符串里有空格&#xff0c;前面提到过了&#xff1a;只能用fgets!! 三.代码实现 #include<bits/stdc.h>//万能头 #define MAX…

SpringBoot-项目引入Redis依赖

在使用Spring Boot开发应用时&#xff0c;可以使用Redis来实现缓存、分布式锁等功能。在编写业务逻辑代码时&#xff0c;可以通过注入RedisTemplate或StringRedisTemplate对象来操作Redis&#xff0c;如存取数据、设置过期时间、删除数据等。同时&#xff0c;还可以使用Redis的…

西电期末1027.判断同构数

一.题目 二.分析与思路 不用把他转成字符串再转成数字之类的&#xff0c;用数学解决就好&#xff01;找出一个数的最后位就是将其对求余啊&#xff0c;找一个数有几位以前也有过啊&#xff0c;那不就过了嘛&#xff01; 三.代码实现 #include<bits/stdc.h>//万能头 in…

Windows.OpenSSL生成ssl证书配置到nginx

一、下载OpenSSL程序安装 到E:\soft\OpenSSL-Win64 二、打开一个CMD控制台窗口&#xff0c;设置好openssl.cnf路径 E: cd E:\soft\OpenSSL-Win64\bin set OPENSSL_CONFE:\soft\OpenSSL-Win64\bin\openssl.cnf 三、在当前目录 E:\soft\OpenSSL-Win64\bin 里创建两个子目录 m…

MySQL 8.0 InnoDB Tablespaces之Temporary Tablespaces(临时表空间)

文章目录 MySQL 8.0 InnoDB Tablespaces之Temporary Tablespaces&#xff08;临时表空间&#xff09;会话临时表空间会话临时表空间的磁盘分配和回收会话临时表空间的创建创建临时表和查看临时表信息会话临时表空间相关的设置参数innodb_temp_tablespaces_dir 全局临时表空间查…

CentOS安装gcc及g++

目录 一、在线安装 二、离线安装 1、收集对应.rpm文件 2、rpm文件上传 3、在该目录下执行安装命令 3、测试 一、在线安装 联网安装比较简单只需使用如下命令即可 yum install gcc yum install gcc-c 二、离线安装 1、收集对应.rpm文件 &#xff08;1&#xff09;、解压…

OS_lab——保护模式之GDT、 Descriptor、Selector、GDTR 及其之间关系

1. 保护模式的相关数据结构 保护模式必要的数据结构定义 • GDT&#xff1a;即为 Global Descriptor Table&#xff08;全局描述符表&#xff09;&#xff0c;又称段描述符表&#xff0c; 为保护模式下的一个数据结构。其中包含多个 descriptor&#xff0c;定义了段的起始地…

pyinstaller生成的exe文件启动时间漫长的原因

加-F慢的原因是&#xff0c;pyinstaller把所有资源文件包括python解释器的依赖文件和库都打包到exe一个文件中&#xff0c;用户打开时&#xff0c;pyinstaller需要先执行一边解压操作&#xff0c;把依赖文件全部解压出来。慢就慢在这里。 如果不加-F&#xff0c;你会发现那些文…

STL标准库与泛型编程(侯捷)笔记3

STL标准库与泛型编程&#xff08;侯捷&#xff09; 本文是学习笔记&#xff0c;仅供个人学习使用。如有侵权&#xff0c;请联系删除。 参考链接 Youbute: 侯捷-STL标准库与泛型编程 B站: 侯捷 - STL Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCo…

常用服务器管理面板整理汇总

服务器管理面板是用于管理和控制服务器的软件&#xff0c;可以帮助管理员更轻松地进行服务器管理和维护。以下是几种常用的服务器管理面板&#xff1a; 1、宝塔面板【官网直达】 宝塔面板是一款服务器运维管理软件&#xff0c;支持Windows和Linux等操作系统&#xff0c;提供了…

《动手学深度学习》学习笔记 第6章 卷积神经网络

本系列为《动手学深度学习》学习笔记 书籍链接&#xff1a;动手学深度学习 笔记是从第四章开始&#xff0c;前面三章为基础知道&#xff0c;有需要的可以自己去看看 关于本系列笔记&#xff1a; 书里为了让读者更好的理解&#xff0c;有大篇幅的描述性的文字&#xff0c;内容很…

TypeScript 从入门到进阶之基础篇(六) 类型(断言 、推论、别名)| 联合类型 | 交叉类型

系列文章目录 TypeScript 从入门到进阶系列 TypeScript 从入门到进阶之基础篇(一) ts基础类型篇TypeScript 从入门到进阶之基础篇(二) ts进阶类型篇TypeScript 从入门到进阶之基础篇(三) 元组类型篇TypeScript 从入门到进阶之基础篇(四) symbol类型篇TypeScript 从入门到进阶…

鱼类识别Python+深度学习人工智能+TensorFlow+卷积神经网络算法

一、介绍 鱼类识别系统。使用Python作为主要编程语言开发&#xff0c;通过收集常见的30种鱼类&#xff08;‘墨鱼’, ‘多宝鱼’, ‘带鱼’, ‘石斑鱼’, ‘秋刀鱼’, ‘章鱼’, ‘红鱼’, ‘罗非鱼’, ‘胖头鱼’, ‘草鱼’, ‘银鱼’, ‘青鱼’, ‘马头鱼’, ‘鱿鱼’, ‘鲇…