LeetCode 算法:杨辉三角 c++

2024-08-29 01:36

本文主要是介绍LeetCode 算法:杨辉三角 c++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 原题链接🔗:杨辉三角
  • 难度:简单⭐️

题目

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

杨辉三角

杨辉三角,又称帕斯卡三角形,是一种将二项式系数以三角形形式排列的数学图形。它在中国最早由北宋数学家贾宪在《释锁算术》中提出,后来南宋数学家杨辉在1261年所著的《详解九章算法》中进行了详细说明,并称之为“开方作法本源”图。杨辉三角不仅揭示了二项展开式的二项式系数的构成规律,还具有许多奇妙的性质,例如每行数字的对称性、中间数字最大等。

杨辉三角的递推公式是每个数等于它上方两个数之和,这一规律被称为杨辉三角的核心。在杨辉三角中,每行的数字之和为 2n - 1,其中 n
是行数,且第 n 行的第 m 个数可以表示为组合数 C(n-1, m-1)。

在欧洲,杨辉三角被称为帕斯卡三角形,因为法国数学家帕斯卡在1654年发现了这一规律,这比杨辉晚了393年,比贾宪晚了约600年。杨辉三角在数学、组合数学、概率论等领域都有广泛的应用,并且随着计算机技术的发展,其计算和应用变得更加便捷和高效。

另外,杨辉三角与文学中的宝塔诗和连环章等有着相似之处,展现了数学与文学的交融之美。在编程实现中,杨辉三角也较为容易构造,可以通过简单的递推算法来生成。

题解

  1. 解题思路:

杨辉三角,又称帕斯卡三角,是一个在数学中非常著名的几何图形,它由数字组成,每行的数字是上一行相邻数字的和。具体来说,杨辉三角的第0行是1,从第1行开始,每个数字是它正上方和左上方的数字之和。例如:

   11 11 2 1
1 3 3 1    
1 4 6 4 1 ... 

LeetCode上的杨辉三角问题通常要求你实现一个函数,根据输入的行数返回对应的杨辉三角行。以下是解决这个问题的一种思路:

  1. 初始化:首先,你需要一个二维数组来存储杨辉三角的每一行。数组的行数等于输入的行数rowIndex

  2. 填充第一行:杨辉三角的第一行总是[1],所以你可以初始化数组的第一行。

  3. 填充后续行:对于每一行,除了第一个和最后一个元素(它们都是1),其他元素都是其正上方和左上方元素的和。

  4. 边界条件:注意,每一行的第一个和最后一个元素都是1,这是杨辉三角的一个特性。

  5. 返回结果:最后,返回填充好的二维数组。

  1. c++ demo:
#include <iostream>
#include <vector>// 函数用于生成杨辉三角的前n行
void generatePascalTriangle(int n) {std::vector<std::vector<int>> triangle;for (int i = 0; i < n; ++i) {std::vector<int> row(i + 1, 1); // 每行开始和结束都是1triangle.push_back(row);// 计算中间的值for (int j = 1; j < i; ++j) {triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];}}// 打印杨辉三角for (const auto& row : triangle) {for (int num : row) {std::cout << num << " ";}std::cout << std::endl;}
}int main() {int numRows;std::cout << "Enter the number of rows for Pascal's Triangle: ";std::cin >> numRows;generatePascalTriangle(numRows);return 0;
}
  • 输出结果:

Enter the number of rows for Pascal’s Triangle: 9
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1

  1. 代码仓库地址:generatePascalTriangle

这篇关于LeetCode 算法:杨辉三角 c++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1116471

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程