代码随想录算法训练营第五十天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III
代码随想录算法训练营第五十天
198.打家劫舍
题目链接:198.打家劫舍
- 确定dp数组以及下标的含义:dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
- 确定递推公式:max(dp[i - 1], dp[i - 2] + nums[i]);,不偷当前节点和偷当前节点哪个获利最大就取哪个
- dp数组如何初始化:dp[0]=nums[0],只有一个必须偷。dp[1]=max(nums[0],nums[1])一共2个元素,只能偷一个最大的
- 确定遍历顺序:从前向后遍历。
- 打印dp数组。
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 1)return nums[0];vector<int> dp(nums.size(), 0);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.size() - 1];}
};
213.打家劫舍II
题目链接:213.打家劫舍II
偷第一家就不能偷最后一家,偷最后一家就不能偷第一家,分别将两种状态求出,再从二者之间找最大值。两种情况分别可以用上题方法求解。
class Solution {
public:int Rob(vector<int>& nums,int start, int end){if(start==end)return nums[start];vector<int> dp(nums.size(), 0);dp[start] = nums[start];dp[start+1] = max(nums[start], nums[start+1]);for (int i = start+2; i <= end; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[end];}int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];int first = Rob(nums,0,nums.size()-2);int last = Rob(nums, 1, nums.size()-1);return max(first,last);}
};
337.打家劫舍III
题目链接:337.打家劫舍III
dp数组表示,每个节点偷当前节点和不偷当前节点可以取得的最大价值。要求当前节点值需要知道左右节点的值,所以是后序遍历。最后再偷根节点和不偷根节点之间取一个最大值即可。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> Rob(TreeNode* cur){if(cur==nullptr)return {0,0};vector<int> left = Rob(cur->left);vector<int> right = Rob(cur->right);vector<int>dp(2);//定义一个dp数组dp[0]表示当前节点不偷可以获得的最大金币,dp[1]表示偷当前节点可以获得的最大金币dp[0] = max(left[0],left[1])+max(right[0],right[1]);//不偷当前节点,那它的子节点可以选择偷或者不偷,左子偷不偷选最大的+右子偷不偷选最大的dp[1] = left[0]+right[0]+cur->val;//偷当前节点,左右子都不能偷,所以等于左不偷+右不偷+当前节点的值return dp;}int rob(TreeNode* root) {return max(Rob(root)[0],Rob(root)[1]);}
};
相关文章:
代码随想录算法训练营第五十天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III
代码随想录算法训练营第五十天 198.打家劫舍 题目链接:198.打家劫舍 确定dp数组以及下标的含义:dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。确定递推公式:max(dp[i - 1],…...
VB.net 进行CAD二次开发(二)
利用参考文献2,添加面板 执行treeControl New UCTreeView()时报一个错误: 用户代码未处理 System.ArgumentException HResult-2147024809 Message控件不支持透明的背景色。 SourceSystem.Windows.Forms StackTrace: 在 System.Windows…...
安徽某高校数据挖掘作业6
1 根据附件中year文件,编辑Python程序绘制年销售总额分布条形图和年净利润分布条形图,附Python程序和图像。 2 根据附件中quarter和quarter_b文件,编辑Python程序绘制2018—2020年销售额和净利润折线图,附Python程序和图像。 3 …...
CMakeLists.txt和Package.xml
CMakeLists.txt和Package.xml CMakeLists.txt 总览 CMakeLists.txt 是用于定义如何构建 ROS (Robot Operating System) 包的 CMake 脚本文件。CMake 是一个跨平台的构建系统,用于自动化编译过程。在 ROS 中,CMakeLists.txt 文件指定了如何编译代码和链…...
Debian常用命令详解
Debian常用命令详解 Debian是一个流行的Linux发行版,它以其稳定性、强大的包管理系统和丰富的软件仓库而著称。对于Debian用户来说,掌握一些常用的命令行工具和命令是日常系统管理和维护的基础。下面,我们将介绍一些Debian系统中常用的命令。…...
代码随想录算法训练营day29|491.递增子序列、46.全排列、47.全排列II
递增子序列 491. 非递减子序列 - 力扣(LeetCode) 非递减子序列,则答案的子集中,需保持下一个元素大于等于前一个元素的顺序,由于题目中指出,所有的子序列长度需大于等于2,考虑当条件为path.siz…...
【ARM Cache 与 MMU 系列文章 7.8 – ARMv8/v9 MMU Table 表分配原理及其代码实现 2】
请阅读【ARM Cache 及 MMU/MPU 系列文章专栏导读】 及【嵌入式开发学习必备专栏】 文章目录 MMU Table 表分配原理及其代码实现MMU Table 分配代码实现MMU Table 表分配原理及其代码实现 在做映射的时候所映射的地址范围最大只能是某一级 level table 中 entry 所能支持的最大…...
SAP PP学习笔记17 - MTS(Make-to-Stock) 按库存生产(策略70)
上几章讲了几种策略,策略10,11,30,40。 SAP PP学习笔记14 - MTS(Make-to-Stock) 按库存生产(策略10),以及生产计划的概要-CSDN博客 SAP PP学习笔记15 - MTS(Make-to-St…...
网页音频提取在线工具有哪些 网页音频提取在线工具下载
别再到处去借会员账号啦。教你一招,无视版权和地区限制,直接下载网页中的音频文件。没有复杂的操作步骤,也不用学习任何代码。只要是网页中播放的音频文件,都可以把它下载到本地保存。 一、网页音频提取在线工具有哪些 市面上的…...
【ARM Cache 系列文章 2.1 -- Cache PoP 及 PoDP 介绍】
请阅读【ARM Cache 及 MMU/MPU 系列文章专栏导读】 及【嵌入式开发学习必备专栏】 文章目录 PoP 及 PoDPCache PoDPCache PoP应用和影响PoP 及 PoDP Cache PoDP 点对深度持久性(Point of Deep Persistence, PoDP)是内存系统中的一个点,在该点达到的任何写操作即使在系统供电…...
一文了解JVM面试篇(上)
Java内存区域 1、如何解释 Java 堆空间及 GC? 当通过 Java 命令启动 Java 进程的时候,会为它分配内存。内存的一部分用于创建 堆空间,当程序中创建对象的时候,就从对空间中分配内存。GC 是 JVM 内部的一 个进程,回收无效对象的内存用于将来的分配。 2、JVM 的主要组成…...
C#WPF控件Textbox绑定浮点型数据限制小数位方法
本文讲解C#WPF控件Textbox绑定浮点型数据限制小数位方法。 XAML中,使用StringFormat来格式化TextBox的文本 <Window x:Class="WpfApp.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.m…...
mysql引入表名称的注意事项
1、遇到问题 mapper中的文件是这样的 解析出来的sql是这样的 sql显示为:select * from ‘tableName’ 2、解决方法 mapper文件种使用${tableName}而不是#{tableName}...
C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍
文章目录 前言一、快速排序非递归二、归并排序五、归并排序非递归总结 前言 C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍 一、快速排序非递归 快速排序非递归的定义 快速排序非递归,需要使用栈来实现。将左右下标分别push到栈中。在栈为…...
学生成绩管理系统(大一大作业)
功能 实现添加,排序,修改,保存等功能 库函数 #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<string.h> 头文件 #define functioncreate(major) void major##compare(mana mn){\int i,j,s…...
数据结构:模拟栈
数据结构:模拟栈 题目描述参考代码 题目描述 输入样例 10 push 5 query push 6 pop query pop empty push 4 query empty输出样例 5 5 YES 4 NO参考代码 #include <iostream>using namespace std;const int N 1000010;int m, x; int q[N]; string op; int…...
02-2.3.6 顺序表和链表的比较
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑💻 此外,《程序员必备技能》专栏和《程序员必备工具》专栏(该专栏暂未开设)日后会逐步更新,感兴趣的小伙伴可以点一下订阅…...
C++ : 模板初阶
标题:C : 模板初阶 水墨不写bug 正文开始: C语言的问题 : 写不完的swap函数 在学习C语言时,我们有一个经常使用的函数swap函数,它可以将两个对象的值交换。 我们通常这样实现它: void swap(int t1,int t2)…...
FFA-Net:用于单图像去雾的特征融合注意力网络
摘要 论文链接:https://arxiv.org/pdf/1911.07559v2 在这篇论文中,我们提出了一种端到端的特征融合注意力网络(FFA-Net)来直接恢复无雾图像。FFA-Net架构由三个关键组件组成: 一种新颖的特征注意力(FA&…...
网工内推 | 联通公司,云计算售前,AWS认证优先
01 联通数字科技有限公司 🔷招聘岗位:云计算售前工程师 🔷职责描述: 1.了解私有云,公有云,混合云等云计算技术知识,了解云计算行业现状及发展趋势。 2.承担区域项目售前工作支持,为…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化
是不是受够了安装了oracle database之后sqlplus的简陋,无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话,配置.bahs_profile后也能解决上下翻页这些,但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可,…...
面试高频问题
文章目录 🚀 消息队列核心技术揭秘:从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"?性能背后的秘密1.1 顺序写入与零拷贝:性能的双引擎1.2 分区并行:数据的"八车道高速公路"1.3 页缓存与批量处理…...
flow_controllers
关键点: 流控制器类型: 同步(Sync):发布操作会阻塞,直到数据被确认发送。异步(Async):发布操作非阻塞,数据发送由后台线程处理。纯同步(PureSync…...
