LeetCode热题100|动态规划Part.1|70.爬楼梯、118.杨辉三角、198.打家劫舍
70.爬楼梯
代码随想录原题,看这篇文章:C++动态规划Part.1|动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯
118.杨辉三角
题目链接:118.杨辉三角
一刷代码
时间复杂度和空间复杂度都造到 O ( n u m R o w s 2 ) O(numRows^2) O(numRows2)了。
基本思路就是先构造一个result存储最终的结果,然后定义一个dp数组来计算每一行的结果。
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> result;for (int i = 0; i < numRows; i++) {vector<int> dp(i + 1, 1); // 行的大小应为i+1if (i >= 2) { // 从第三行开始填充中间的数for (int j = 1; j < i; j++) {dp[j] = result[i - 1][j - 1] + result[i - 1][j]; // 正确使用result中的前一行}}result.push_back(dp);}return result;}
};
思路
很容易看到一个主要的性质:
杨辉三角中每个数字等于上一行的左右两个数字之和。
-
确定dp数组下标和含义
dp[i][j]等于第i行和第j列的值。 -
确定递推公式
递推公式很容易分析出来:
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
也就是每个数字等于上一行左右两个数字之和,但是需要注意的是, 每一行的最左边和最右边的数字必须是1. -
初始化dp数组
这里应该如何初始化呢?
最直接的方式就是直接全部初始化成1,因为每一行除了第一个和最后一个元素,我们都能通过递推公式进行推导 -
确定遍历顺序
在leetcode的题目展示上面已经看的很清楚了,
外循环从上往下遍历,内循环从左往右遍历。
这里需要注意的是,由于每一行的元素个数都是变化的,所以关于行的初始化一定要在外循环中处理。代码如下:
for (int i = 0; i < numRows; ++i) { //先遍历行dp[i].resize(i + 1); //将第i行的向量大小调整为i+1dp[i][0] = dp[i][i] = 1;for (int j = 1; j < i; +=j) { //再遍历列dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];}
}
- 打印dp数组
还是比较简单的,这里就不写了。
CPP代码
其实思路还是很简单的,不过代码实现要一点小技巧,
- 在这里我们先创建一个大小为numRows的二维向量,其中每一行都是一个空的向量。在这种情况下,ret的初始状态是一个包含5行的二维向量,但每行都没有元素。
vector<vector<int>> dp(numRows);
- 然后我们在外循环中给每一行向量再调整大小,这样我们在原数组上做操作,空间复杂度一下就下来了。
for (int i = 0; i < numRows; ++i) {dp[i].resize(i + 1);...
}
总体代码如下:
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> dp(numRows);for (int i = 0; i < numRows; ++i) {dp[i].resize(i + 1);dp[i][0] = dp[i][i] = 1;for (int j = 1; j < i; ++j) {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];}}return ret;}
};
198.打家劫舍
代码随想录原题,看这篇文章:C++动态规划Part8|198.打家劫舍、213.打家劫舍II、198.打家劫舍III
相关文章:
LeetCode热题100|动态规划Part.1|70.爬楼梯、118.杨辉三角、198.打家劫舍
70.爬楼梯 代码随想录原题,看这篇文章:C动态规划Part.1|动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯 118.杨辉三角 题目链接:118.杨辉三角 一刷代码 时间复杂度和空间复杂度都造到 O ( n u m R o w s 2 ) O(num…...
python 根据网址和关键词批量下载影像
最近用到了GLASS的LAI产品,但这个产品的文件夹分得很细,我需要的影像又有8个瓦片,一个一个点击很麻烦,于是探索了批量下载的方法 一、下载1幅 import requests import re import os import requests import re# 网页URLurl &…...
爬虫-无限debug场景 解决方式
解决无限debug 场景1 1. 鼠标右键 选择 continue to here(此处不停留)2. 鼠标右键 选择 edite breakpoint 设置 10 保证条件不成立 这行永远不执行3.方法置空 1. 方法调用加断点2. 控制台 setInterval function name() {}4. 替换文件 5. hoo…...
[链表专题]力扣206, 203, 19
1. 力扣206 : 反转链表 (1). 题 : 图略 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。示例 1:输入:head [1,2,3,4,5] 输出:[5,4,3,2,1] 示例 2:输入:head [1,2] 输出&#x…...
秋招后端开发面试题 - MySQL基础
目录 MySQL基础前言面试题MySQL 基础篇Mysql 的基础架构?MySQL 的长连接和短连接长连接引起的异常重启问题?说一下 MySQL 执行一条查询语句的内部执行过程?MySQL 查询缓存的功能有何优缺点?MySQL 的常用引擎都有哪些?I…...
力扣每日一题113:路径总和||
题目 中等 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSu…...
Thinkphp5 中常见的session 操作方法
在 ThinkPHP 框架中,session 是用于在多个页面或请求之间存储用户信息的机制。以下是在 ThinkPHP 中进行 session 常见操作的一些示例: 启动 Session 在 ThinkPHP 中,通常不需要手动启动 Session,因为框架会在应用启动时自动处理…...
inBuilder 低代码平台新特性推荐 - 第十八期
今天来给大家带来的是inBuilder低代码平台特性推荐系列第十八期——表单设计器集成预约日历组件。 一、场景介绍 项目上希望用日历的形式展示某地点在一段时间内的预约记录,表单设计器新增支持创建日历预约视图,并配置预约属性。 二、运行效果 三、前…...
部署xwiki服务需要配置 hibernate.cfg.xml如何配置?
1. 定位 hibernate.cfg.xml 文件 首先,确保您可以在 Tomcat 的 XWiki 部署目录中找到 hibernate.cfg.xml 文件: cd /opt/tomcat/latest/webapps/xwiki/WEB-INF ls -l hibernate.cfg.xml如果文件存在,您可以继续编辑它。如果不存在ÿ…...
1376:信使(msner)
【解题思路】 每个哨所是一个顶点,哨所与哨所之间的通信线路为边,两哨所间通讯花费的时间为边的权值。记第一个哨所为顶点s,信息从第一个哨所传递到表示为顶点x的某哨所可能有多条路径,每条传送路径有一个花费的时间&…...
Hadoop3:HDFS的架构组成
一、官方文档 我这里学习的是Hadoop3.1.3版本,所以,查看的也是3.1.3版本的文档 Architecture模块最下面 二、HDFS架构介绍 HDFS架构的主要组成部分,是一下四个部分 1、NameNode(NN) 就是Master节点,它是集群管理者。 1、管…...
P2910 [USACO08OPEN] Clear And Present Danger S
Problem: P2910 [USACO08OPEN] Clear And Present Danger S 文章目录 思路解题方法复杂度Code 思路 这是一个图论问题,我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先,我们需要构建一个距离矩阵&am…...
ES6 对象方面的新特性
ES6(ECMAScript 2015)为JavaScript语言增加了很多新特性,包括对象字面量属性的简写、计算属性名、方法的简写、对象的解构赋值、Object.assign()方法复制对象属性、Object.is()比较两个值等。以下是一些在ES6中经常使用的对象方法:…...
GO语言核心30讲 进阶技术 (第一部分)
原站地址:Go语言核心36讲_Golang_Go语言-极客时间 一、数组和切片 1. 两者最大的不同:数组的长度是固定的,而切片的长度是可变的。 2. 可以把切片看成是对数组的一层封装,因为每个切片的底层数据结构中,一定会包含一…...
[力扣题解]225. 用队列实现栈
题目:225. 用队列实现栈 思路 用一个队列模拟栈; 假设有数字:1,2,3; pop 队列里是这样的存的:3,2,1; 作为一个栈,应该弹出最后进来的那一个3&…...
Leetcode—2105. 给植物浇水 II【中等】
2024每日刷题(131) Leetcode—2105. 给植物浇水 II 实现代码 class Solution { public:int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {int size plants.size();int i 0;int j size - 1;int capA capacityA;in…...
wordpress外贸建站公司歪建站新版网站上线
wordpress外贸建站公司 歪猫建站 歪猫WordPress外贸建站,专业从事WordPress多语言外贸小语种网站建设与外贸网站海个推广、Google SEO搜索引擎优化等服务。 https://www.waimaoyes.com/dongguan...
关于二手车系统学习--登录模块
1.样式1-17行 <div class="cheader"><div style="width: 80%;margin: 0 auto;line-height: 50px;padding-top: 10px"><el-row><el-col:span="5"style="font-size: 20px;cursor: pointer;color: #00ae66;font-weight: …...
若依生成代码的步骤
1.创建表,要有注释 2.导入表 3.创建主菜单 4.修改表 5.生成代码 6.把代码复制到自己的程序中:复制表、后端、前端 7.重启后端,如果有问题则clean 8.回到浏览器可以看到正常显示了生成的页面...
深度学习论文: LightGlue: Local Feature Matching at Light Speed
深度学习论文: LightGlue: Local Feature Matching at Light Speed LightGlue: Local Feature Matching at Light Speed PDF: https://arxiv.org/pdf/2306.13643 PyTorch代码: https://github.com/shanglianlm0525/CvPytorch PyTorch代码: https://github.com/shanglianlm0525/…...
别再硬编码了!用注解+工厂模式,5分钟为你的Java应用扩展一个新PLC协议(ModbusTCP/S7为例)
工业物联网中Java协议扩展的优雅实践:注解驱动与工厂模式深度整合 工业物联网(IIoT)平台的开发者们经常面临一个棘手问题:如何在不重构核心代码的情况下,快速接入各种PLC设备协议?想象一下这样的场景:你的系统已经稳定…...
Android 应用间文件共享:FileProvider 配置与实战解析
1. 为什么需要FileProvider? 在Android开发中,每个应用都有自己的私有存储空间,这些目录默认是其他应用无法访问的。这种设计保证了应用数据的安全性,但同时也带来了一个问题:当我们需要与其他应用共享文件时该怎么办&…...
【Java Web学习 | 第九篇】JavaScript(3) 数组+函数
【Java Web学习 | 第九篇】JavaScript(3) - 数组与函数进阶(2026最新版) 本篇对数组和函数进行更深入、实用的讲解,这是 Java Web 开发中处理后端返回数据(JSON 数组/对象列表)和封装业务逻辑的核心技能。 由于你特别…...
DAMO-YOLO智能视觉系统作品集:多场景零售货架检测效果惊艳展示
DAMO-YOLO智能视觉系统作品集:多场景零售货架检测效果惊艳展示 1. 零售视觉检测的新标杆 走进现代零售空间,商品陈列的艺术背后隐藏着复杂的运营挑战。传统的人工巡检方式已经难以满足快节奏零售环境的需求,这正是DAMO-YOLO智能视觉系统大放…...
foobox-cn:重塑foobar2000视听体验的智能界面解决方案
foobox-cn:重塑foobar2000视听体验的智能界面解决方案 【免费下载链接】foobox-cn DUI 配置 for foobar2000 项目地址: https://gitcode.com/GitHub_Trending/fo/foobox-cn 你是否曾因音乐播放器界面过于简陋而错失沉浸式的听觉享受?当功能性凌驾…...
手把手教你用RK3576开发板驱动RC522读卡器:一个SPI实战项目的完整配置流程
手把手教你用RK3576开发板驱动RC522读卡器:一个SPI实战项目的完整配置流程 在嵌入式开发领域,能够独立完成一个从硬件连接到软件驱动的完整项目,是每个开发者成长的必经之路。RK3576作为一款性能强劲的开发板,搭配常见的RC522读卡…...
音乐标签编辑器:让本地音乐元数据管理效率提升90%的开源工具
音乐标签编辑器:让本地音乐元数据管理效率提升90%的开源工具 【免费下载链接】music-tag-web 音乐标签编辑器,可编辑本地音乐文件的元数据(Editable local music file metadata.) 项目地址: https://gitcode.com/gh_mirrors/mu/…...
Fish Speech 1.5开源可部署:模型权重分离存储与热更新机制设计
Fish Speech 1.5开源可部署:模型权重分离存储与热更新机制设计 1. 引言:语音合成的新突破 当你听到一段自然流畅的语音,是否曾想过它可能完全由AI生成?Fish Speech 1.5正是这样一个令人惊叹的技术成果——它能够仅凭10-30秒的参…...
如何突破思维导图协作瓶颈?云端协同与知识管理新方案
如何突破思维导图协作瓶颈?云端协同与知识管理新方案 【免费下载链接】kityminder 百度脑图 项目地址: https://gitcode.com/gh_mirrors/ki/kityminder 在数字化办公环境中,思维导图作为梳理思路、规划项目的重要工具,其价值已得到广泛…...
Cursor Pro免费激活终极指南:3种方法永久解锁AI编程助手
Cursor Pro免费激活终极指南:3种方法永久解锁AI编程助手 【免费下载链接】cursor-free-vip [Support 0.45](Multi Language 多语言)自动注册 Cursor Ai ,自动重置机器ID , 免费升级使用Pro 功能: Youve reached your t…...
