当前位置: 首页 > news >正文

代码随想录算法训练营第五十天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

代码随想录算法训练营第五十天

198.打家劫舍

题目链接:198.打家劫舍

  1. 确定dp数组以及下标的含义:dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
  2. 确定递推公式:max(dp[i - 1], dp[i - 2] + nums[i]);,不偷当前节点和偷当前节点哪个获利最大就取哪个
  3. dp数组如何初始化:dp[0]=nums[0],只有一个必须偷。dp[1]=max(nums[0],nums[1])一共2个元素,只能偷一个最大的
  4. 确定遍历顺序:从前向后遍历。
  5. 打印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.打家劫舍 题目链接&#xff1a;198.打家劫舍 确定dp数组以及下标的含义&#xff1a;dp[i]&#xff1a;考虑下标i&#xff08;包括i&#xff09;以内的房屋&#xff0c;最多可以偷窃的金额为dp[i]。确定递推公式&#xff1a;max(dp[i - 1],…...

VB.net 进行CAD二次开发(二)

利用参考文献2&#xff0c;添加面板 执行treeControl New UCTreeView()时报一个错误&#xff1a; 用户代码未处理 System.ArgumentException HResult-2147024809 Message控件不支持透明的背景色。 SourceSystem.Windows.Forms StackTrace: 在 System.Windows…...

安徽某高校数据挖掘作业6

1 根据附件中year文件&#xff0c;编辑Python程序绘制年销售总额分布条形图和年净利润分布条形图&#xff0c;附Python程序和图像。 2 根据附件中quarter和quarter_b文件&#xff0c;编辑Python程序绘制2018—2020年销售额和净利润折线图&#xff0c;附Python程序和图像。 3 …...

CMakeLists.txt和Package.xml

CMakeLists.txt和Package.xml CMakeLists.txt 总览 CMakeLists.txt 是用于定义如何构建 ROS (Robot Operating System) 包的 CMake 脚本文件。CMake 是一个跨平台的构建系统&#xff0c;用于自动化编译过程。在 ROS 中&#xff0c;CMakeLists.txt 文件指定了如何编译代码和链…...

Debian常用命令详解

Debian常用命令详解 Debian是一个流行的Linux发行版&#xff0c;它以其稳定性、强大的包管理系统和丰富的软件仓库而著称。对于Debian用户来说&#xff0c;掌握一些常用的命令行工具和命令是日常系统管理和维护的基础。下面&#xff0c;我们将介绍一些Debian系统中常用的命令。…...

代码随想录算法训练营day29|491.递增子序列、46.全排列、47.全排列II

递增子序列 491. 非递减子序列 - 力扣&#xff08;LeetCode&#xff09; 非递减子序列&#xff0c;则答案的子集中&#xff0c;需保持下一个元素大于等于前一个元素的顺序&#xff0c;由于题目中指出&#xff0c;所有的子序列长度需大于等于2&#xff0c;考虑当条件为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)

上几章讲了几种策略&#xff0c;策略10&#xff0c;11&#xff0c;30&#xff0c;40。 SAP PP学习笔记14 - MTS&#xff08;Make-to-Stock) 按库存生产&#xff08;策略10&#xff09;&#xff0c;以及生产计划的概要-CSDN博客 SAP PP学习笔记15 - MTS&#xff08;Make-to-St…...

网页音频提取在线工具有哪些 网页音频提取在线工具下载

别再到处去借会员账号啦。教你一招&#xff0c;无视版权和地区限制&#xff0c;直接下载网页中的音频文件。没有复杂的操作步骤&#xff0c;也不用学习任何代码。只要是网页中播放的音频文件&#xff0c;都可以把它下载到本地保存。 一、网页音频提取在线工具有哪些 市面上的…...

【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显示为&#xff1a;select * from ‘tableName’ 2、解决方法 mapper文件种使用${tableName}而不是#{tableName}...

C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍

文章目录 前言一、快速排序非递归二、归并排序五、归并排序非递归总结 前言 C语言数据结构快速排序的非递归、归并排序、归并排序的非递归等的介绍 一、快速排序非递归 快速排序非递归的定义 快速排序非递归&#xff0c;需要使用栈来实现。将左右下标分别push到栈中。在栈为…...

学生成绩管理系统(大一大作业)

功能 实现添加&#xff0c;排序&#xff0c;修改&#xff0c;保存等功能 库函数 #include<stdio.h> #include<stdlib.h> #include<windows.h> #include<string.h> 头文件 #define functioncreate(major) void major##compare(mana mn){\int i,j,s…...

数据结构:模拟栈

数据结构&#xff1a;模拟栈 题目描述参考代码 题目描述 输入样例 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 顺序表和链表的比较

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏&#xff0c;今后还会不断更新。&#x1f9d1;‍&#x1f4bb; 此外&#xff0c;《程序员必备技能》专栏和《程序员必备工具》专栏&#xff08;该专栏暂未开设&#xff09;日后会逐步更新&#xff0c;感兴趣的小伙伴可以点一下订阅…...

C++ : 模板初阶

标题&#xff1a;C : 模板初阶 水墨不写bug 正文开始&#xff1a; C语言的问题 &#xff1a; 写不完的swap函数 在学习C语言时&#xff0c;我们有一个经常使用的函数swap函数&#xff0c;它可以将两个对象的值交换。 我们通常这样实现它&#xff1a; void swap(int t1,int t2)…...

FFA-Net:用于单图像去雾的特征融合注意力网络

摘要 论文链接&#xff1a;https://arxiv.org/pdf/1911.07559v2 在这篇论文中&#xff0c;我们提出了一种端到端的特征融合注意力网络&#xff08;FFA-Net&#xff09;来直接恢复无雾图像。FFA-Net架构由三个关键组件组成&#xff1a; 一种新颖的特征注意力&#xff08;FA&…...

网工内推 | 联通公司,云计算售前,AWS认证优先

01 联通数字科技有限公司 &#x1f537;招聘岗位&#xff1a;云计算售前工程师 &#x1f537;职责描述&#xff1a; 1.了解私有云&#xff0c;公有云&#xff0c;混合云等云计算技术知识&#xff0c;了解云计算行业现状及发展趋势。 2.承担区域项目售前工作支持&#xff0c;为…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...