Leetcode 118 杨辉三角

目录

  • 一、问题描述
  • 二、示例及约束
  • 三、代码
    • 方法一:数学
  • 四、总结

一、问题描述

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

三、代码

方法一:数学

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);//创建二维数组ret,初始数组的行数为numRows
        for (int i = 0; i < numRows; i++) {
            ret[i].resize(i + 1);//每行初始化为i + 1列
            ret[i][0] = ret[i][i] = 1;  //每行最左和最右元素固定为1
            /*每个数是它左上方和右上方的数的和
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }*/
            for (int j = 1; j <= i / 2; j++) {
            //对于杨辉三角而言,左右是对称的,因此遍历一半即可
                ret[i][j] = ret[i - 1][j -1] + ret[i - 1][j];
                if (i - j != j) {
                //当i是奇数的时候,最中间的数是加法得到的,不能对称赋值得到
                    ret[i][i - j] = ret[i][j];//对称赋值
                }
            }
        }
        return ret;
    }
};

四、总结

时间复杂度:
方法一:O( n u m R o w s 2 numRows^2 numRows2)。
空间复杂度:
方法一:O(1),不考虑返回的数组空间。

方法时间复杂度空间复杂度
方法一O( n u m R o w s 2 numRows^2 numRows2)O(1)

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

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

相关文章

电子防潮柜出厂前要经过哪些测试?

电子防潮柜在发货前应执行一系列质量控制测试以确保其功能正常、性能稳定且能够满足用户存储物品对湿度控制的需求。以下是沐渥电子防潮柜出厂前的测试流程&#xff1a; 1&#xff09;除湿性能测试&#xff1a;检查并验证防潮柜能否按照设定的湿度目标值准确运行&#xff0c;可…

燃冬之yum、vim和你

了解了很多指令和权限&#xff0c;搞点真枪实弹来瞅瞅 学Linux不是天天就在那掰扯指令玩&#xff0c;也不是就研究那个权限 准备好迎接Linux相关工具的使用了么码农桑~ yum 软件包 什么是软件包呢&#xff1f; 首先来举个生活中常见点的例子&#xff1a;比如我的手机是华为…

盘点数据资产管理十大活动职能 优化企业数据资产管理和应用

在当今的数字化时代&#xff0c;数据已成为企业最宝贵的资产之一&#xff0c;在上篇文章中我们对数据资产管理进行了初步的介绍。 上篇文章指路&#x1f449;什么是数据资产管理&#xff1f;详谈数据资产管理的难点与发展现状&#xff01; 有效的数据资产管理不仅能提升企业的…

【JAVA】阿里技术官耗时三个月整理的Java核心知识点

在裁员风波的席卷之下&#xff0c;IT行业弥漫着浓厚的焦虑和不安。面对如此动荡的环境&#xff0c;一个共识日益凸显&#xff1a;提升个人价值至关重要。 这不仅仅是指薪资上的数字增长&#xff0c;更重要的是在职场中、在专业领域、在技术上不断取得突破&#xff0c;并塑造自…

固态继电器:推进可再生能源系统

随着可再生能源系统的发展&#xff0c;太阳能系统日益成为现代能源解决方案的先锋。在这种背景下&#xff0c;固态继电器&#xff08;SSR&#xff09;&#xff0c;特别是光耦固态继电器的利用变得日益突出。本文旨在深入探讨SSR在可再生能源系统中的多方位应用&#xff0c;重点…

ClickHouse 数据类型、表引擎与TTL

文章目录 数据类型注意事项 表引擎1.TinyLog 引擎2.MergeTree 引擎3.ReplacingMergeTree 引擎4.AggregatingMergeTree 引擎5.SummingMergeTree 引擎6.CollapsingMergeTree 引擎7.Distributed 引擎 TTL列级 TTL表级TTL 数据类型 ClickHouse 数据类型Java 数据类型数据范围UInt8…

基于FaceNet的人脸识别

⚠申明&#xff1a; 未经许可&#xff0c;禁止以任何形式转载&#xff0c;若要引用&#xff0c;请标注链接地址。 全文共计10077字&#xff0c;阅读大概需要10分钟 &#x1f308;更多学习内容&#xff0c; 欢迎&#x1f44f;关注&#x1f440;【文末】我的个人微信公众号&#…

Python二进制文件转换为文本文件

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 在日常编程中&#xff0c;我们经常会遇到需要将二进制文件转换为文本文件的情况。这可能是因…

最详细的 Windows 下 PyTorch 入门深度学习环境安装与配置 GPU 版 土堆教程

最详细的 Windows 下 PyTorch 入门深度学习环境安装与配置 CPU GPU 版 | 土堆教程 Windows 下 PyTorch 入门深度学习环境安装与配置 GPU 版 教程大纲如何使用此教程快速开始版本 Windows下判断有无NVIDIA GPU安装Anaconda作用流程下载安装 Anaconda 创建虚拟环境利用conda或者…

谁是存储器市场下一个“宠儿”?

AI浪潮对存储器提出了更高要求&#xff0c;高容量、高性能存储产品重要性正不断凸显&#xff0c;存储产业技术与产能之争也因此愈演愈烈&#xff1a;NAND Flash领域&#xff0c;闪存堆叠层数持续提升&#xff1b;DRAM领域HBM持续扩产&#xff0c;技术不断迭代&#xff0c;同时3…

Github上不去?进来,我教你

目录 一、复制Github的服务器地址 二、打开C盘下的hosts配置文件 三、编辑hosts 四、刷新DNS 五、本教程资源来源 一、复制以下Github的各服务器地址 # GitHub520 Host Start 140.82.112.26 alive.github.com 140.82.113.6 api.github.com…

docker-MySQL 8 主从搭建

一.目录结构&#xff1a; 我是在/home目录下&#xff0c;建立个sql文件夹&#xff1a; 二、配置文件 1.mysql配置 mysql-master下.conf文件配置 ###### [mysqld] server-id1 # 启用二进制日志 log-binmaster-bin # 指定需要复制的数据库 binlog-do-dbtest_db # 指定二进制日…

为什么工业锅炉必须要清洗?-智渍洁

锅炉经过长时间运行&#xff0c;不可避免的出现了水垢、锈蚀问题&#xff0c;锅炉形成水垢的主要原因是给水中带有硬度成分&#xff0c;经过高温、高压的不断蒸发浓缩以后&#xff0c;在炉内发生一系列的物理、化学反应&#xff0c;最终在受热面上形成坚硬、致密的水垢。 水垢是…

【EMQX】使用websocket订阅EMQX数据

需求&#xff1a;某平台希望通过 websocket 来订阅 EMQX平台上的某些 Topic数据进行处理 1、EMQX 服务配置 前提是EMQX服务正常安装运行了&#xff0c;如果EMQX服务未安装的话&#xff0c;详见以下文章关于如何安装部署服务&#xff1a; 搭建自己的MQTT服务器、实现设备上云(W…

windows11编译3dslicer_问题总结

编译前准备 CMake&#xff1a;版本>3.16.3&#xff08;避免使用3.21.0&#xff0c;3.25.0-3.25.2&#xff0c;这些版本&#xff0c;可能会出现build错误&#xff09;。Git&#xff1a;版本>1.7.10&#xff0c;安装完git&#xff0c;一定要在cmd里面试一试&#xff0c;是…

网络安全之弱口令与命令爆破(上篇)(技术进阶)

目录 一&#xff0c;什么是弱口令&#xff1f; 二&#xff0c;为什么会产生弱口令呢&#xff1f; 三&#xff0c;字典的生成 四&#xff0c;使用Burpsuite工具弱口令爆破 总结 一&#xff0c;什么是弱口令&#xff1f; 弱口令就是容易被人们所能猜到的密码呗&#xff0c;…

docker部署前端项目(二)遇到的问题

1、docker版本号 只有1.13.1 因为使用 sudo yum install docker &#xff08;下载到的是旧版&#xff09; 解决&#xff1a;下载新版 报错一&#xff1a; unable to prepare context: unable to evaluate symlinks in Dockerfile path: Lstat /root/Proiects/dist/Dockerfil…

如何在PostgreSQL中创建并使用窗口函数来进行复杂的分析查询?

文章目录 解决方案1. 了解窗口函数的基本概念2. 常用的窗口函数3. 使用示例示例 1&#xff1a;计算每行销售数据的累计销售额示例 2&#xff1a;计算每行销售数据相对于前一行销售额的增长率 结论 PostgreSQL 提供了一套强大的窗口函数&#xff08;Window Functions&#xff09…

NumPy简单学习(需要结合书本)

NumPy简单学习&#xff08;需要结合书本&#xff1a;Python数据分析与应用&#xff09; 文章目录 NumPy简单学习&#xff08;需要结合书本&#xff1a;Python数据分析与应用&#xff09;前言导库&#xff1a; 一、大概内容1.掌握NumPy数组对象ndarray&#xff08;1&#xff09;…

水电气能耗管理云平台

安科瑞薛瑶瑶18701709087/17343930412 能耗管理云平台采用泛在物联、云计算、大数据、移动通讯、智能传感器等技术手段可为用户提供能源数据采集、统计分析、能效分析、用能预警、设备管理等服务&#xff0c;平台可以广泛应用于多种领域。