【LeetCode】探索杨辉三角模型
一、题目描述
力扣原题
- 首先我们要来了解一下题目本身在说些什么,通过下方的动图我们可以更加清楚地看到杨辉三角是怎样一步步生成的。给到的示例中我们通过输入杨辉三角的行数,然后通过计算得到这个杨辉三角的每一行是什么具体的数值
二、模型选择
首先我们要做的第一件事就是去选择正确的求解模型
- 首先第一点,我们要来对比一下使用C语言求解和C++求解有什么不同,以下是题目已经给出的函数接口
- 如果读者有学习过 C语言的指针 和 C++的引用 的话就可以知道,C++的祖师爷为什么要发明出引用这个东西,目的就是为了脱离C语言中非常繁杂的指针
我可以试着来分析一下如何使用C语言来进行求解,首先我们来看到的是这个 返回值
int**
- 为什么要返回
int**
呢,原因就在于对于我们这个杨辉三角来说,虽然呈现的是一个三角形的样子,但是呢其底层的实现其实还是一个二维数组,所以在函数内部我们肯定要去开辟出一个二维数组,读者可以通过下面这张图再来回顾一下有关二级指针的知识点(忘记了可以去看看指针相关文章)
- 看完了返回值后,我们再来看看另外的两个参数,第一个是这个
returnSize
,其代表的是整个二维矩阵的行数,而returnColumnSizes
代表的则是每一行的列数。 - 但为何它们的类型一个是一级指针
int*
,另一个则是二级指针int**
呢?如果你有看过 二叉树练习题之二叉树的遍历 的话就可以知道它们都叫做输出型参数
- 在讲解 函数栈帧 的时候我们说到过这个函数的形参是实参的一份临时拷贝,内部形参的改动是不会影响实参的,所以我们在做二叉树题目的时候如果对这个参数没有做特殊处理的话在不同的递归层中就会出现 覆盖问题
- 所以我们若是想让形参内部的变化带动外部一起修改的话,就需要外部传递变量的地址进来,那对于地址而言就需要使用 指针 来进行接收,一级指针的地址就需要二级指针来接收
所以就这么来看,我们若是使用C语言来求解本题的话,就会变得很麻烦
- 那这个时候就可以使用我们心爱的C++了💖
class Solution {
public:vector<vector<int>> generate(int numRows) {}
};
- 在C++中呢,我们一般不会使用指针来模拟二维数组,而是会采取
vector<vector<int>>
来进行表示
三、思路分析 + 代码详解
接下去我们就来分析一下这道题的思路🔍
- 还记得下面这个动图吗,仔细观察我们可以发现每一行的第一个和最后一个数字都是1。而且中间空缺处的方块都是其 左上方的数字 + 右上方的数字
- 具体地可以看以下的图示
【思路简述】:说一下我是如何去求解这道题的
- 首先的话我们肯定需要先去定义出一个有关
vector
的二维矩阵
vector<vector<int>> vv;
- 接下去呢便要为这个二维矩阵开辟出合适的大小来容纳,这里便可以使用到我们在
vector
中所学习的【resize】接口,既改变了size
,又改变了capacity
vv.resize(numRows);
- 因为矩阵中的每一行的第一个元素和最后一个元素都是1,所以我先去遍历这个矩阵,将所有的值设置为
0
,接下去呢再固定地将每一行的第一个元素vv[i][0]
和最后一个元素vv[i][i]
都设置为1
for(size_t i = 0;i < vv.size(); ++i)
{// 首先将二维数组中的所有元素初始化为0vv[i].resize(i + 1, 0);// 然后将每一行的第一个和最后一个元素初始化为1vv[i][0] = vv[i][i] = 1;
}
- 接下去呢,就要去计算每一行的具体数值了,通过两层for循环去遍历这个二维矩阵,接下去呢我们只对数值为0的位置进行修改,因为每行的第一列和最后一列已经为1了,所以我们去修改的只是中间的那一部分
for(size_t i = 0;i < vv.size(); ++i)
{for(size_t j = 0;j < vv[i].size(); ++j){if(vv[i][j] == 0){// 右上方:vv[i - 1][j]// 左上方:vv[i - 1][j - 1]vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}
}
对于当前的这个值就等于其上方的那一个数和上方左侧的那一个数之和
vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
整体代码展示:
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows);for(size_t i = 0;i < vv.size(); ++i){// 首先将二维数组中的所有元素初始化为0vv[i].resize(i + 1, 0);// 然后将每一行的第一个和最后一个元素初始化为1vv[i][0] = vv[i][i] = 1;}for(size_t i = 0;i < vv.size(); ++i){for(size_t j = 0;j < vv[i].size(); ++j){if(vv[i][j] == 0){// 右上方:vv[i - 1][j]// 左上方:vv[i - 1][j - 1]vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];}}}return vv;}
};
运行结果:
相关文章:

【LeetCode】探索杨辉三角模型
一、题目描述 力扣原题 首先我们要来了解一下题目本身在说些什么,通过下方的动图我们可以更加清楚地看到杨辉三角是怎样一步步生成的。给到的示例中我们通过输入杨辉三角的行数,然后通过计算得到这个杨辉三角的每一行是什么具体的数值 二、模型选择 首先…...

Qt 中引入ffmpeg 动态库
1、前期准备 在qt引入ffmpeg动态库的时候,需要准备ffmpeg的动态库和头文件。 2、打开qt项目 在qt项目的.pro文件中添加以下几行代码 INCLUDEPATH $$PWD/thirtLib/ffmpeg4.2/include win32: LIBS -L$$PWD/thirtLib/ffmpeg4.2/lib/ -lavcodec -lavdevice -lavf…...
工程师是怎样对待开源 qt
工程师如何对待开源 本文是笔者作为一个在知名科技企业内从事开源相关工作超过 20 年的工程师,亲身经历或者亲眼目睹很多工程师对待开源软件的优秀实践,也看到了很多 Bad Cases,所以想把自己的一些心得体会写在这里,供工程师进行…...
Maven中Servlet的坐标为什么要添加<scope>provided</scope>
Maven中Servlet的坐标 在Maven中,我们使用坐标(Coordinates)来唯一标识一个依赖库。对于Servlet,其坐标通常是指定servlet-api包。在使用Servlet时,我们需要将其添加到项目的依赖中,以便在编译、运行和测试…...

联发科CEO:未获准向华为供货,换机潮已过去,手机需求不会更差
据钜亨网报道,联发科近期召开了业绩说明会。蔡力行,该公司副董事长兼首席执行官,表明当前手机市场需求保持稳定,并且随着过去两年用户更换潮的过去,对手机市场明年有一定期望。 根据蔡力行的指示,联发科正在…...
2023年DevOps和云趋势报告!
要点 ●云创新已从革命性阶段转变为演进性阶段,重点是迁移和重新架构工作负载。云空间已发展为提供对可扩展资源和托管服务的按需访问,强调简化交互并减少团队的认知负担。 ●人工智能 (AI) 和大型语言模型 (LLM) 可以通过解决认知过载问题并支持即时管…...

怎么学习CSS相关技术知识? - 易智编译EaseEditing
学习CSS技术是前端开发中的重要一环,它用于控制网页的样式和布局,使网页更加美观和易于使用。以下是学习CSS技术的几个方面: 基本语法和选择器: 了解CSS的基本语法,学习如何使用选择器来选择HTML元素并应用样式。 样…...

Qt 2. QSerialPortInfo显示串口信息
在ex2.pro 添加: QT serialport//main.cpp #include "ex2.h" #include <QtSerialPort/QtSerialPort> #include <QApplication>int main(int argc, char *argv[]) {QApplication a(argc, argv);Ex2 w;w.show();QList<QSerialPortInfo>…...
linux or mac 查看进程的pid和占有的端口
1.查看谁占有了什么端口? lsof -i:<占用端口> [rootgit-lab gitlab]# lsof -i:8929 COMMAND PID USER FD TYPE DEVICE SIZE/OFF NODE NAME docker-pr 25090 root 4u IPv4 140059875 0t0 TCP *:8929 (LISTEN) docker-pr 25096 root …...

8.2Jmeter5.1:察看结果树的响应结果乱码
【问题描述】 Jmeter察看结果树的响应结果乱码 原因:jmeter.properties未设置语言 【解决方案】 修改jmeter.properties的属性,然后重启Jmeter # The encoding to be used if none is provided (default ISO-8859-1) sampleresult.default.encodingut…...
vscode 快捷键
今天好闲 就记一些学的东西吧~ vscode 快捷键 快速生成头文件注释:Ctrlalti 快速生成方法注释:Ctrlaltt 新建窗口:CtrlShiftn 查找:Ctrlf 替换:Ctrlh 替换所有:CtrlAltEnter 打开上一个编辑器:…...
【Antv G6】导出图片
需求 将Antv G6生成的树形图导出成图片 代码 <div style"height: calc(100% - 50px);"><div id"miniMap" class"minimap"></div><div id"containerG6" ref"containerG6" class"containerWrap&…...
shared_ptr
源码路径: /opt/rh/devtoolset-10/root/usr/include/c/10/bits/shared_ptr_base.h D:\wsl-ubuntu20.04\rootfs\usr\include\c\9\bits\shared_ptr_base.h 类原型: template<typename _Tp, _Lock_policy _Lp>class __shared_ptr: public __shared_pt…...
ChatGPT + Stable Diffusion + 百度AI + MoviePy 实现文字生成视频,小说转视频,自媒体神器!(二)
ChatGPT Stable Diffusion 百度AI MoviePy 实现文字生成视频,小说转视频,自媒体神器!(二) 前言 最近大模型频出,但是对于我们普通人来说,如何使用这些AI工具来辅助我们的工作呢,或者参与进入我们的生活…...
git提交的时候Changes not staged for commit
git删除和修改一些文件之后,git add -A之后就使用git commit -m "提交最新代码"后报错 On branch master Your branch is up to date with origin/master.Changes not staged for commit:但是使用git push origin master怎么都提交不上去,解决…...

03_使用execle表生成甘特图
背景 每次排期都需要话很多时间 很可能排期还不对头 这时候需要一个表能看到 1.什么时候项目结束 开始 转阶段 2.当前手上的活能不能做完 当前阶段手上有多少活 3.产品经理每次修改完计划迅速排期 甘特图生成 execle表生成 1.需要使用亿图创建甘特图 2.把当前的甘特图数据进…...
linux基础命令-ls
“ls” 命令是 Linux 系统中用来列出目录内容的常用命令。它显示当前工作目录中的文件和子目录列表。下面将详细解释 “ls” 命令的用法以及示例: 命令语法: ls [选项] [目录] 常用选项: -l: 以长格式(long format&a…...

Chrome浏览器中的vue插件devtools的下载方式(使用Chrome应用商店/科学上网情况下)
目录 devtools对前端来说的好处——开发预览、远程调试、性能调优、Bug跟踪、断点调试等 下载步骤: 测试阶段: 最近做项目要使用devtools这个vue插件。 devtools对前端来说的好处——开发预览、远程调试、性能调优、Bug跟踪、断点调试等 下载步骤…...

7、Kubernetes核心技术 - Secret
目录 一、Secret概述 二、Secret 三种类型 2.1、Opaque 2..2、kubernetes.io/dockerconfigjson 2.3、kubernetes.io/service-account-token 三、Secret创建 3.1、命令行方式创建 Secret 3.2、yaml方式创建 Secret 四、Secret解码 五、Secret使用 5.1、将 Secret 挂载…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...

聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...