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/…...
忍者像素绘卷效果实测:同一Prompt下不同步数对像素锐度影响对比分析
忍者像素绘卷效果实测:同一Prompt下不同步数对像素锐度影响对比分析 1. 测试背景与目的 忍者像素绘卷作为一款基于Z-Image-Turbo深度优化的图像生成工具,其独特的16-Bit复古游戏美学风格吸引了大量创作者。在实际使用中,我们发现"描绘…...
5分钟搞定电脑风扇噪音!FanControl超详细配置指南让你告别“飞机起飞“
5分钟搞定电脑风扇噪音!FanControl超详细配置指南让你告别"飞机起飞" 【免费下载链接】FanControl.Releases This is the release repository for Fan Control, a highly customizable fan controlling software for Windows. 项目地址: https://gitcod…...
从GlobeLand30数据到统计报表:QGIS分区统计+Excel,打造你的地表覆盖分析工作流
从GlobeLand30到专业报表:QGISExcel高效地表覆盖分析全流程 地表覆盖数据是理解区域生态环境、规划土地利用的重要基础。GlobeLand30作为30米分辨率的全球地表覆盖数据集,为研究者提供了高精度的分析素材。但如何将这些数据转化为可操作的见解࿱…...
Phi-4-mini-reasoning惊艳效果:自动识别题目所属数学分支并推荐解法策略
Phi-4-mini-reasoning惊艳效果:自动识别题目所属数学分支并推荐解法策略 1. 模型介绍 Phi-4-mini-reasoning是微软推出的3.8B参数轻量级开源模型,专为数学推理、逻辑推导和多步解题等强逻辑任务设计。这个模型主打"小参数、强推理、长上下文、低延…...
如何在一天内彻底改变你的人生(How to Fix Your Entire Life in 1 Day)
如何在一天内彻底改变你的人生 作者:丹科伊(Dan Koe) 你大概率会放弃自己的新年决心。 这没什么大不了的。大多数人都会这样(研究显示失败率高达80%至90%),因为大多数人并非真的在内心深处渴望改变。也就是…...
3步掌握Vortex:让250+游戏模组管理像专业开发者一样简单
3步掌握Vortex:让250游戏模组管理像专业开发者一样简单 【免费下载链接】Vortex Vortex: Nexus-Mods开发的游戏模组管理器,用于简化模组的安装和管理过程。 项目地址: https://gitcode.com/gh_mirrors/vor/Vortex 价值定位:重新定义游…...
从FasterRCNN到自定义检测器:SimpleDet扩展开发完全手册
从FasterRCNN到自定义检测器:SimpleDet扩展开发完全手册 【免费下载链接】simpledet A Simple and Versatile Framework for Object Detection and Instance Recognition 项目地址: https://gitcode.com/gh_mirrors/si/simpledet SimpleDet是一个简单且多功能…...
Qwen-Image镜像实战:基于RTX4090D,轻松实现图片问答与内容分析
Qwen-Image镜像实战:基于RTX4090D,轻松实现图片问答与内容分析 1. 引言:Qwen-Image镜像的核心价值 在当今多模态AI技术快速发展的背景下,能够同时理解图像和文本的视觉语言模型正变得越来越重要。Qwen-Image作为通义千问系列中的…...
PKSM终极指南:从第一世代到第八世代的宝可梦存档管理神器
PKSM终极指南:从第一世代到第八世代的宝可梦存档管理神器 【免费下载链接】PKSM Gen I to GenVIII save manager. 项目地址: https://gitcode.com/gh_mirrors/pk/PKSM PKSM是一款功能强大的免费开源宝可梦存档管理工具,支持从第一世代到第八世代的…...
网站SEO优化与网站内容更新的关系_企业网站SEO优化与行业特点的关系
<h3 id"seo_seo">网站SEO优化与网站内容更新的关系_企业网站SEO优化与行业特点的关系</h3> <p>在当今数字化时代,网站的SEO优化与内容更新之间有着密切的关系。这不仅关系到企业网站的流量,还直接影响企业的品牌形象和市场竞…...
