热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

帕斯卡三角形生成算法

给定行数numRows,生成帕斯卡三角形的前numRows行。例如,当numRows为5时,返回的结果应为:[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]。

问题描述:

根据给定的行数 numRows,生成帕斯卡三角形(Pascal's Triangle)的前 numRows 行。

例如,如果 numRows = 5,则返回:

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

中文解释:

给定行数 numRows,生成帕斯卡三角形的前 numRows 行。

例如,如果 numRows = 5,则返回:

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

解决方案:

初次接触这道题时,可能会觉得有简便方法,但实际操作中需要按照定义逐步构建。帕斯卡三角形的构造规则如下:

  • 第一行只有一个元素:1。
  • 第二行有两个元素:1, 1。
  • 从第三行开始,每一行的元素数量等于行号。每行的第一个和最后一个元素都是 1,中间的元素是上一行相邻两个元素之和。

具体实现可以通过以下步骤完成:

  • 初始化一个空的结果列表 result 和一个临时列表 last 用于存储上一行的数据。
  • 遍历从 1 到 numRows 的每一行,对于每一行:
    • 创建一个新的行列表 row,并将第一个元素设为 1。
    • 如果当前行大于 2,则根据上一行的数据填充中间元素。
    • 将新生成的行添加到结果列表中,并更新 last 为当前行。

时间复杂度为 O(n²),其中 n 是行数。

1 class Solution {
2 public:
3 vectorint>> generate(int numRows) {
4 if( numRows <&#61; 0 ) {
5 return vectorint>>();
6 }
7
8 vectorint>> result;
9 vector<int> last &#61; {1};
10 for( int i &#61; 1; i <&#61; numRows; i&#43;&#43; ) {
11 vector<int> row &#61; {1};
12 if( i >&#61; 2 ) {
13 for( int j &#61; 1; j 1; j&#43;&#43; ) {
14 row.push_back(last[j-1] &#43; last[j]);
15 }
16 }
17 row.push_back(1 );
18 result.push_back(row);
19 last &#61; row;
20 }
21 return result;
22 }
23 };


推荐阅读
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • 尽管某些细分市场如WAN优化表现不佳,但全球运营商路由器和交换机市场持续增长。根据最新研究,该市场预计在2023年达到202亿美元的规模。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 深入解析Android自定义View面试题
    本文探讨了Android Launcher开发中自定义View的重要性,并通过一道经典的面试题,帮助开发者更好地理解自定义View的实现细节。文章不仅涵盖了基础知识,还提供了实际操作建议。 ... [详细]
  • PyCharm下载与安装指南
    本文详细介绍如何从官方渠道下载并安装PyCharm集成开发环境(IDE),涵盖Windows、macOS和Linux系统,同时提供详细的安装步骤及配置建议。 ... [详细]
  • 本文详细介绍如何使用Python进行配置文件的读写操作,涵盖常见的配置文件格式(如INI、JSON、TOML和YAML),并提供具体的代码示例。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • 本文介绍了如何使用JQuery实现省市二级联动和表单验证。首先,通过change事件监听用户选择的省份,并动态加载对应的城市列表。其次,详细讲解了使用Validation插件进行表单验证的方法,包括内置规则、自定义规则及实时验证功能。 ... [详细]
  • 本文介绍了一款用于自动化部署 Linux 服务的 Bash 脚本。该脚本不仅涵盖了基本的文件复制和目录创建,还处理了系统服务的配置和启动,确保在多种 Linux 发行版上都能顺利运行。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
author-avatar
李磊g114826
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有