Leetcode.118 杨辉三角

题目链接

Leetcode.118 杨辉三角 easy

题目描述

给定一个非负整数 n u m R o w s numRows numRows,生成「杨辉三角」的前 n u m R o w s 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 ≤ n u m R o w s ≤ 30 1 \leq numRows \leq 30 1numRows30

解法:动态规划

在 杨辉三角 中,每一行比前一行多一个元素;

在每一行中,第一个元素和最后一个元素都是 1 1 1

我们用 f [ i ] [ j ] f[i][j] f[i][j] 表示第 i i i 行的,下标为 j j j 的元素:

f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i − 1 ] [ j ] f[i][j] = f[i - 1][j-1] + f[i-1][j] f[i][j]=f[i1][j1]+f[i1][j]

时间复杂度: O ( n 2 ) O(n^2) O(n2)

C++代码:

class Solution {
public:vector<vector<int>> generate(int n) {vector<vector<int>> f{{1}};for(int len = 2;len <= n;len++){vector<int> temp;int i = len - 1;for(int j = 0;j < len;j++){if(j == 0 || j == len - 1) temp.push_back(1);else{temp.push_back(f[i - 1][j - 1] + f[i - 1][j]);}}f.push_back(temp);}return f;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

go、java、.net、C#、nodejs、vue、react、python程序问题进群咨询

1、面试辅导 2、程序辅导 3、一对一腾讯会议辅导 3、业务逻辑辅导 4、各种bug帮你解决。 5、培训小白 6、顺利拿到offer

Streamlit项目:基于讯飞星火认知大模型开发Web智能对话应用

文章目录 1 前言2 API获取3 官方文档的调用代码4 Streamlit 网页的搭建4.1 代码及效果展示4.2 Streamlit相关知识点 5 结语 1 前言 科大讯飞公司于2023年8月15日发布了讯飞认知大模型V2.0&#xff0c;这是一款集跨领域知识和语言理解能力于一体的新一代认知智能大模型。前日&a…

Python入门教程 | Python简介和环境搭建

Python 简介 Python是一种高级编程语言&#xff0c;由荷兰人Guido van Rossum于1991年创建。它以其简单易学、可读性强和丰富的生态系统而受到广泛喜爱。它被广泛应用于各个领域&#xff0c;包括Web开发、科学计算、数据分析、人工智能等。 Python的特点 简洁易读&#xff1a…

深度学习实战49-基于卷积神经网络和注意力机制的汽车品牌与型号分类识别的应用

大家好,我是微学AI,今天给大家介绍一下深度学习实战49-基于卷积神经网络和注意力机制的汽车品牌与型号分类识别的应用,该项目就像是一只智慧而敏锐的眼睛,专注地凝视着汽车世界。这个项目使用PyTorch作为强有力的工具,提供了一个深度学习的舞台,让我们能够设计和训练一个…

JAVA结合AE(Adobe After Effects)AE模板文件解析生成视频实现类似于逗拍(视频DIY)的核心功能

最近看抖音上有很多各种视频表白生成的直播而且直播间人很多&#xff0c;于是就思考如何实现的视频内的文字图片内容替换的呢 &#xff0c;答案需要用到类似与逗拍一样的视频DIY的功能&#xff0c;苦于我是java&#xff0c;百度了半天没有办法和思路&#xff0c;总不能为了一个…

[JavaWeb]【五】web后端开发-Tomcat SpringBoot解析

目录 一 介绍Tomcat 二 基本使用 2.1 解压绿色版 2.2 启动TOMCAT 2.3 关闭TOMCAT 2.4 常见问题 2.5 修改端口号 2.6 部署应用程序 三 SpringBootWeb入门程序解析 前言&#xff1a;tomcat与SpringBoot解析 一 介绍Tomcat 二 基本使用 2.1 解压绿色版 2.2 启动TOMCAT 2…

国标GB28181视频平台EasyGBS通过对应密钥上传到其他平台展示的详细步骤来啦!

国标GB28181协议视频平台EasyGBS是基于国标GB28181协议的视频云服务平台&#xff0c;支持多路设备同时接入&#xff0c;并对多平台、多终端分发出RTSP、RTMP、FLV、HLS、WebRTC等格式的视频流。平台可提供视频监控直播、云端录像、云存储、检索回放、智能告警、语音对讲、平台级…

算法通关村第5关【青铜】| Hash和队列的特征

1.Hash基础 &#xff08;1&#xff09;基础 哈希也称为散列&#xff0c;通过算法变成固定长度的输出值&#xff0c;存入对应的位置 例如这个算法为取模算法&#xff0c;indexnumber 模 7 存入1到15 &#xff08;2&#xff09;碰撞处理 当多个元素映射到同一位置上时就产生…

【C语言】线性搜索数组

题目 给一个数&#xff0c;判定这个数是否在数组a[]中&#xff0c;若在则输出该数在数组中的位置&#xff0c;若不在则输出-1 代码 #include<stdio.h> int search(int key, int a[], int len) {int ret -1;for(int i0; i<len; i){if(key a[i]){ret i;break;}}ret…

企业百家号蓝V认证后,百度营销基木鱼落地页如何嵌入百家号中

首先搭建百度营销基木鱼落地页 在我们的百度营销后台&#xff0c;点击基木鱼跳转至百度营销基木鱼页面&#xff0c;在我的站点位置&#xff0c;可以创建H5站点&#xff0c;PC站点等&#xff0c;创建完成后可以点击复制基木鱼落地页的链接。 注意事项 1、企业百家号需要进行…

打造全球浪漫:2023七夕节出海品牌的国际化营销创意

随着时间的流转&#xff0c;2023年的七夕节即将到来&#xff0c;这是一年一度的浪漫佳节&#xff0c;被众多情侣们期待已久。而对于出海品牌来说&#xff0c;七夕节不仅是一个传统的节日&#xff0c;更是一个极具营销价值的时刻。在这个浪漫的节日里&#xff0c;出海品牌可以借…

神经网络基础-神经网络补充概念-54-softmax回归

概念 Softmax回归&#xff08;Softmax Regression&#xff09;是一种用于多分类任务的机器学习算法&#xff0c;特别是在神经网络中常用于输出层来进行分类。它是Logistic回归在多分类问题上的推广。 原理 Softmax回归的主要思想是将原始的线性分数&#xff08;得分&#xf…

57从零开始学Java之一文详解String字符串的底层实现原理

作者&#xff1a;孙玉昌&#xff0c;昵称【一一哥】&#xff0c;另外【壹壹哥】也是我哦 千锋教育高级教研员、CSDN博客专家、万粉博主、阿里云专家博主、掘金优质作者 前言 在之前的两篇文章中&#xff0c;壹哥给大家介绍了String字符串及其常用的API方法、常用编码、正则表达…

Redis、Memcache和MongoDB的区别

>>Memcached Memcached的优点&#xff1a; Memcached可以利用多核优势&#xff0c;单实例吞吐量极高&#xff0c;可以达到几十万QPS&#xff08;取决于key、value的字节大小以及服务器硬件性能&#xff0c;日常环境中QPS高峰大约在4-6w左右&#xff09;。适用于最大程度…

windows电脑系统自带的画图工具如何实现自由拼图

1.首先选中你要拼接的第一张图片&#xff0c;右键选着编辑&#xff0c;会自动打开自带的画图工具 然后就是打开第一张图片&#xff0c;如下图所示 接着就是将画布托大&#xff0c;如下图所示。 然后点击选择&#xff0c;选择下面的空白区域&#xff0c;选着区域的范围要比准备拼…

手把手教你在虚拟机中部署Kubernetes集群(K8S)

我们在上面&#xff1a;VM部署CentOS并且设置网络 部署好了服务器。接下来需要准备三个服务器分别为 master节点&#xff1a;master 192.168.171.7 node节点&#xff1a;node1 192.168.171.6 node节点&#xff1a;node2 192.168.171.4 此步骤需要启动三台虚拟机&#xff…

12 正则表达式 | HTTP协议相关介绍

文章目录 正则表达式re模块最基础操作&#xff08;匹配开头&#xff09;匹配单个字符匹配多个字符匹配开头结尾匹配分组对于group的理解r的作用re 模块高级用法compilesearchfindall易错点 sub直接替换函数替换 split 根据匹配进行切割字符串&#xff0c;并返回一个列表 python…

Maven之Servlet 版本问题

maven-archetype-webapp 骨架的 Servlet 版本问题 通过 maven-archetype-webapp 骨架去创建 java web 项目时&#xff0c;自动生成的 web.xml 配置文件所使用的 Servlet 的版本比较低&#xff08;2.3&#xff09;&#xff0c;而在低版本的 Servlet 中 EL 表达式默认是关闭的。…