当前位置: 首页 > news >正文

leetcode118. 杨辉三角,老题又做

leetcode118. 杨辉三角

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

蓝桥杯有个类似的题目,我曾写过题解。

在这里插入图片描述

题目分析

杨辉三角是一个经典的数学问题,每一行的第一个和最后一个数字都是1,其他位置的数字是它上方和左上方数字之和。这个问题可以通过动态规划的方式来解决。

算法步骤

  1. 初始化结果数组 res 和临时数组 t
  2. 特殊处理第一行,将 1 加入 t,然后将 t 加入 res
  3. 如果 numRows 为1,直接返回 res
  4. 初始化二维数组 nums 用于记录中间结果,大小为 40x40(根据题目需求设定)。
  5. 使用双重循环遍历每一行,计算当前行的数值:
    • 对于每一行的第一个和最后一个数字,直接设置为1。
    • 对于其他位置的数字,计算方式为 nums[i-1][j-1] + nums[i-1][j]
  6. 将计算结果存入 res

算法流程

开始
初始化res和t
numRows是否等于1
返回res
初始化nums
双重循环计算每一行
将计算结果存入res
返回res

具体代码

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> res;vector<int> t;t.push_back(1);res.push_back(t);if(numRows==1) return res;int nums[40][40]={0};nums[1][1]=1;for(int i=2;i<=numRows;i++){vector<int> temp;temp.push_back(1);nums[i][1]=1;for(int j=2;j<=i-1;j++)  //i=4 {int sum=nums[i-1][j-1]+nums[i-1][j];temp.push_back(sum);nums[i][j]=sum;}temp.push_back(1);nums[i][i]=1;res.push_back(temp);}return res;}
};

算法分析

  • 时间复杂度: O(numRows^2),因为需要计算每一行的数值。
  • 空间复杂度: O(numRows^2),因为需要存储每一行的数值。
  • 易错点: 在计算每一行的数值时,需要注意边界条件,即每一行的第一个和最后一个数字都是1。

相似题目

题目链接
118. 杨辉三角https://leetcode.cn/problems/pascals-triangle/
119. 杨辉三角 IIhttps://leetcode.cn/problems/pascals-triangle-ii/
剑指 Offer 47. 礼物的最大价值https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/

相关文章:

leetcode118. 杨辉三角,老题又做

leetcode118. 杨辉三角 给定一个非负整数 numRows&#xff0c;生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中&#xff0c;每个数是它左上方和右上方的数的和。 示例 1: 输入: numRows 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2: 输入: numRows 1…...

进程(一)(22)

1.进程是什么 进程是程序执行的过程&#xff0c;会去分配内存资源&#xff0c;cpu的调度。正在运行的程序叫进程。 并发&#xff1a;同一时刻可以同时完成多个任务。 进程: 是操作系统对正在运行的程序的抽象。进程不仅包括程序的代码&#xff0c;还包括程序的执行状态、内存…...

Excel“取消工作表保护”忘记密码并恢复原始密码

文章目录 1.前言2.破解步骤3. 最终效果4.参考文献 1.前言 有时候别人发来的Excel中有些表格不能编辑&#xff0c;提示如下&#xff0c;但是又不知道原始密码 2.破解步骤 1、打开您需要破解保护密码的Excel文件&#xff1b; 2、依次点击菜单栏上的视图—宏----录制宏&#xf…...

WPS关闭后,进程依然在后台运行的解决办法

问题 wps启动后 在启动wps后&#xff0c;什么都不做&#xff0c;打开进程管理器&#xff0c;发现居然运行了3个wps进程&#xff1a; win10只会显示wps进程&#xff1a; win11显示比较准确&#xff1a; 关闭后 在关闭wps&#xff0c;再去任务管理器查看&#xff0c;发现在…...

SQL每日一练-0816

今日SQL题&#xff1a;计算每个项目的年度收入增长率 难度系数&#xff1a;&#x1f31f;☆☆☆☆☆☆☆☆☆ 1、题目要求 计算每个项目每年的收入总额&#xff0c;并计算项目收入环比增长率。找出每年收入增长率最高的项目。输出结果显示年份、项目ID、项目名称、项…...

直方图均衡化

概念 直方图均衡化是图像处理领域中利用图像直方图对对比度进行调整的方法&#xff0c;通过拉伸像素强度分布范围来增强图像对比度。 原理 均衡化指的是把一个分布 (给定的直方图) 映射 到另一个分布 (一个更宽更统一的强度值分布)&#xff0c;从而令强度值分布会在整个范围内…...

Golang | Leetcode Golang题解之第342题4的幂

题目&#xff1a; 题解&#xff1a; func isPowerOfFour(n int) bool {return n > 0 && n&(n-1) 0 && n%3 1 }...

数学建模学习(116):全面解析梯度下降算法及其在机器学习中的应用与优化

文章目录 1.梯度下降简介1.1 梯度下降的数学原理1.2 学习率的选择2 梯度下降变体3.梯度下降优化器3.1 动量法(Momentum)3.2 AdaGrad3.3 RMSprop3.4 Adam3.5 Python 使用不同优化器训练线性回归模型4.案例:使用梯度下降优化加利福尼亚房价预测模型4.1. 数据准备4.2. 模型训练…...

[mysql][sql]mysql查询表大小

select table_schema as 数据库, table_name as 表名, table_rows as 记录数, truncate(data_length/1024/1024, 2) as 数据容量(MB), truncate(index_length/1024/1024, 2) as 索引容量(MB) from information_schema.tables where 11 and table_schemadb001 order by table_ro…...

8.16 mysql主从数据库(5.7版本)与python的交互及mycat

mysql数据库基本操作&#xff1a; [rootm ~]# tar -xf mysql-5.7.44-linux-glibc2.12-x86_64.tar.gz 解压压缩包 [rootm ~]# ls anaconda-ks.cfg mysql-5.7.44-linux-glibc2.12-x86_64 mysql-5.7.44-linux-glibc2.12-x86_64.tar.gz [rootm ~]# cp -r mysql-5.7.44-lin…...

项目问题 | CentOS 7停止维护导致yum失效的解决办法

目录 centos停止维护意味着yum相关源伴随失效。 报错&#xff1a; 解决方案&#xff1a;将图中四个文件替换掉/etc/yum.repos.d/目录下同名文件 资源提交在博客头部&#xff0c;博客结尾也提供文件源码内容 CentOS-Base.repo CentOS-SCLo-scl.repo CentOS-SCLo-scl-rh.rep…...

【Docker】Docker Compose(容器编排)

一、什么是 Docker Compose docker-compose 是 Docker 官方的开源项目&#xff0c;使用 python 编写&#xff0c;实现上调用了 Docker 服务的 API 进行容器管理及编排&#xff0c;其官方定义为定义和运行多个 Docker 容器的应用。 docker-compose 中有两个非常重要的概念&…...

嵌入式初学-C语言-二九

C语言编译步骤 预处理编译汇编链接 什么是预处理 预处理就是在源文件&#xff08;如.c文件&#xff09;编译之前&#xff0c;所进行的一部分预备操作&#xff0c;这部分操作是由预处理程序自动完成&#xff0c;当源文件在编译时&#xff0c;编译器会自动调用预处理指令的解析…...

0x03 ShowDoc 文件上传漏洞(CNVD-2020-26585)复现

参考&#xff1a;ShowDoc文件上传漏洞&#xff08;CNVD-2020-26585&#xff09;_showdoc漏洞-CSDN博客 一、fofa 搜索使用该工具的网站 网络空间测绘&#xff0c;网络空间安全搜索引擎&#xff0c;网络空间搜索引擎&#xff0c;安全态势感知 - FOFA网络空间测绘系统 "S…...

【大模型从入门到精通34】开源库框架LangChain 利用LangChain构建聊天机器人1

这里写目录标题 利用LangChain构建聊天机器人介绍介绍对话型聊天机器人构建环境环境变量和平台设置 加载文档和创建向量存储高级检索技术对话上下文和记忆纳入聊天历史会话缓冲内存 构建对话检索链环境设置与API密钥配置选择合适的语言模型版本Q&A系统设置 利用LangChain构…...

魔法糖果工厂

LYA 是一家魔法糖果工厂的新任管理员。工厂生产的魔法糖果有七种颜色&#xff0c;分别用字母 a、b、c、d、e、f、g 表示。这些糖果被排列在一条传送带上&#xff0c;准备进行包装。为了提高效率&#xff0c;工厂引进了一台智能包装机器人。这个机器人可以按照预设的指令序列来包…...

NVM安装管理node.js版本(简单易懂)

一、前言 1.1 简介 NVM&#xff08;Node Version Manager&#xff09;是 node.js 的版本管理器&#xff0c;用 shell 脚本切换机器中不同版本的 nodejs。 Nodejs为什么需要多个版本&#xff1f; 有经验的开发者可能遇到过&#xff0c;某个依赖包明确nodejs是某个版本&#…...

第1章-04-Chrome及Chrome Driver安装及测试

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌&#xff0c;CSDN博客专家&#xff0c;阿里云社区专家博主&#xff0c;2023年CSDN全站百大博主。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师&am…...

【Linux】SSH 隧道转发场景搭建

ssh建立隧道转发 A设备&#xff1a;没有公网IP地址的本地设备&#xff0c;如本地内网服务器&#xff08;需要能通公网&#xff09; B设备&#xff1a;有公网IP地址的服务器&#xff0c;可以是云服务器 C设备&#xff1a;终端设备&#xff0c;想通过公网服务器B访问到设备A 要…...

前后端部署-服务器linux中安装数据库Mysql8

一、登录Xshell7 && 开放Mysql 3306端口&#xff0c; Redis 6379 端口 二、手动部署MySQL数据库 1.运行以下命令&#xff0c;更新YUM源。 sudo rpm -Uvh https://dev.mysql.com/get/mysql80-community-release-el7-7.noarch.rpm 2.运行以下命令&#xff0c;安装My…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...