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

Day48|leetcode 198.打家劫舍、213.打家劫舍II、打家劫舍|||

leetcode 198.打家劫舍

题目链接:198. 打家劫舍 - 力扣(LeetCode)

视频链接:动态规划,偷不偷这个房间呢?| LeetCode:198.打家劫舍_哔哩哔哩_bilibili

题目概述

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路

本题只说不能相邻两个房间偷,所以说只要不是相邻两个房间的话,不论你选择第几个房间都可以,只要偷的钱最多就好,没有太多限制因素。

依旧是动规五部曲

1.确定dp数组含义:

dp[i]:考虑下标i(包括i)之内的房屋,最多可以偷的金额是dp[i]。

2.确定递推公式:

偷i:dp[i]=nums[i]+dp[i-2]

不偷i:dp[i]=dp[i-1]

所以递推公式:dp[i]=max(nums[i]+dp[i-2],dp[i-1])。

3.数组初始化:

dp[0]=nums[0]

dp[1]=max(nums[0],nums[1])

4.确定遍历顺序:

从前向后

5.打印dp数组:

198.打家劫舍

 

代码实现 

lass Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 0) return 0;if(nums.size() == 1) return nums[0];vector<int> dp(nums.size());dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);for(int i = 2;i < nums.size();i++) {dp[i] = max(dp[i - 2] + nums[i],dp[i - 1]);}return dp[nums.size() - 1];}
};

leetcode 213.打家劫舍II

题目链接:213. 打家劫舍 II - 力扣(LeetCode)

视频链接:动态规划,房间连成环了那还偷不偷呢?| LeetCode:213.打家劫舍II_哔哩哔哩_bilibili

题目概述

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 3:

输入:nums = [1,2,3]
输出:3

思路

其实本题和上题差不多,就是本题变成了一个环,不利于思考。但是,我们可以把环拆成一个线性数组,那么就会有三种情况:(考虑只是考虑,并不一定会偷)

1.考虑不包含首尾元素,如图所示:

213.打家劫舍II

2.考虑包含首元素,如图所示:

213.打家劫舍II1

3.考虑包含尾元素,如图所示:

213.打家劫舍II2

 第二种和第三种情况把第一种情况包含了,所以本题只是把数组做了一个截取,传进主函数去取最大值而已。

代码实现 

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2); // 情况二int result2 = robRange(nums, 1, nums.size() - 1); // 情况三return max(result1, result2);}// 198.打家劫舍的逻辑int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size());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 - 2] + nums[i], dp[i - 1]);}return dp[end];}
};

leetcode 337.打家劫舍 III

题目链接:337. 打家劫舍 III - 力扣(LeetCode)

视频链接:动态规划,房间连成树了,偷不偷呢?| LeetCode:337.打家劫舍3_哔哩哔哩_bilibili

题目概述

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为  root。

除了root 之外,每栋房子有且只有一个"父"房子与之相连。一番侦察之后,聪明的小偷意识到"这个地方的所有房屋的排列类似于一棵二叉树"。如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。

在不触动警报的情况下 ,小偷能够盗取的最高金额 。

 

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

思路

这道题目算是树形dp的入门题目,以递归三部曲加动规五部曲来讲:

1.确定递归函数的参数和返回值

返回值:一个长度为2的数组。

确定dp数组含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。

2.确定终止条件

遇空就返回。

3.确定遍历顺序

后序遍历

4.确定单层递归的逻辑

当前节点偷:val1 = cur->val + left[0] + right[0]

当前节点不偷:val2 = max(left[0], left[1]) + max(right[0], right[1])

5.举例推导dp数组

 

代码实现 

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}// 长度为2的数组,0:不偷,1:偷vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);// 偷cur,那么就不能偷左右节点。int val1 = cur->val + left[0] + right[0];// 不偷cur,那么可以偷也可以不偷左右节点,则取较大的情况int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};

相关文章:

Day48|leetcode 198.打家劫舍、213.打家劫舍II、打家劫舍|||

leetcode 198.打家劫舍 题目链接&#xff1a;198. 打家劫舍 - 力扣&#xff08;LeetCode&#xff09; 视频链接&#xff1a;动态规划&#xff0c;偷不偷这个房间呢&#xff1f;| LeetCode&#xff1a;198.打家劫舍_哔哩哔哩_bilibili 题目概述 你是一个专业的小偷&#xff0c;…...

Mysql001:Mysql概述以及安装

前言&#xff1a;本课程将从头学习Mysql&#xff0c;以我的工作经验来说&#xff0c;sql语句真的太重要的&#xff0c;现在互联网所有的一切都是建立在数据上&#xff0c;因为互联网的兴起&#xff0c;现在的数据日月增多&#xff0c;每年都以翻倍的形式增长&#xff0c;对于数…...

如何调用api接口获取到商品数据

要调用API接口获取商品数据&#xff0c;需要进行以下步骤&#xff1a; 1.确定API接口 首先需要确定要使用的API接口&#xff0c;可以通过搜索引擎或者相关文档来查找适合的API接口。以淘宝开放平台为例&#xff0c;可以使用淘宝的商品信息查询API接口来获取商品数据。 2.注册…...

http请求方式过滤器与拦截器的区别

get:获取查询数据(查询)post:数据的提交&#xff0c;新增操作(增加)put:向服务端发送数据、改变信息&#xff0c;侧重点在于对数据的修改操作delete:数据库数据的删除head:一般用来判断类型、根据返回状态确定资源是否存在、资源是否更新以及更新的时间等 过滤器与拦截器的区别…...

大语言模型初学者指南 (2023)

大语言模型 (LLM) 是深度学习的一个子集&#xff0c;它正在彻底改变自然语言处理领域。它们是功能强大的通用语言模型&#xff0c;可以针对大量数据进行预训练&#xff0c;然后针对特定任务进行微调。这使得LLM能够拥有大量的一般数据。如果一个人想将LLM用于特定目的&#xff…...

日常生活小技巧 -- 单位换算

开发过程中经常需要需要单位换算的地方。 可以使用工具进行转换&#xff1a; 工具&#xff1a;单位转换 常用单位&#xff1a; 1、角度转换 1弧度&#xff08;rad&#xff09; 180/PI 度&#xff08;deg&#xff09; 57.29577951308232 度&#xff08;deg&#xff09; 1度…...

利用深度蛋白质序列嵌入方法通过 Siamese neural network 对 virus-host PPIs 进行精准预测【Patterns,2022】

研究背景&#xff1a; 病毒感染可以导致多种组织特异性损伤&#xff0c;所以 virus-host PPIs 的预测有助于新的治疗方法的研究&#xff1b;目前已有的一些 virus-host PPIs 鉴定或预测方法效果有限&#xff08;传统实验方法费时费力、计算方法要么基于蛋白结构或基因&#xff…...

opencv 车牌号的定位和识别+UI界面识别系统

目录 一、实现和完整UI视频效果展示 主界面&#xff1a; 识别结果界面&#xff1a;&#xff08;识别车牌颜色和车牌号&#xff09; 查看历史记录界面&#xff1a; 二、原理介绍&#xff1a; 车牌检测->图像灰度化->Canny边缘检测->膨胀与腐蚀 边缘检测及预处理…...

如何使用CSS实现一个自适应两栏布局,其中一栏固定宽度,另一栏自适应宽度?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 使用Float属性⭐ 使用Flexbox布局⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为那些对Web开发感…...

【PostgreSQL】导出数据库表(或序列)的结构和数据

导出 PostgreSQL 数据库的结构和数据 要导出 PostgreSQL 数据库的结构和数据&#xff0c;你可以使用 pg_dump 命令行工具。pg_dump 可以生成一个 SQL 脚本文件&#xff0c;其中包含了数据库的结构&#xff08;表、索引、视图等&#xff09;以及数据。下面是如何使用 pg_dump 导…...

Arcgis colorRmap

arcgis中colorRmap对应的名称&#xff1a; 信息来源&#xff1a;https://developers.arcgis.com/documentation/common-data-types/raster-function-objects.htm 在arcpy中使用方法&#xff1a; import arcpy cr arcpy.mp.ColorRamp("Yellow to Red")python中 ma…...

[JDK8环境下的HashMap类应用及源码分析] capacity实验

🌹作者主页:青花锁 🌹简介:Java领域优质创作者🏆、Java微服务架构公号作者😄、CSDN博客专家 🌹简历模板、学习资料、面试题库、技术互助 🌹文末获取联系方式 📝 系列文章目录 [Java基础] StringBuffer 和 StringBuilder 类应用及源码分析 [Java基础] 数组应用…...

【自动驾驶】TI SK-TDA4VM 开发板上电调试,AI Demo运行

1. 设备清单 TDA4VM Edge AI 入门套件【略】USB 摄像头(任何符合 V4L2 标准的 1MP/2MP 摄像头,例如:罗技 C270/C920/C922)全高清 eDP/HDMI 显示屏最低 16GB 高性能 SD 卡连接到互联网的 100Base-T 以太网电缆【略】UART电缆外部电源或电源附件要求: 标称输出电压:5-20VDC…...

基于LOF算法的异常值检测

目录 LOF算法简介Sklearn官网LOF算法应用实例1Sklearn官网LOF算法应用实例2基于LOF算法鸢尾花数据集异常值检测读取数据构造数据可视化&#xff0c;画出可疑异常点LOF算法 LOF算法简介 LOF异常检测算法是一种基于密度的异常检测算法&#xff0c;基于密度的异常检测算法主要思想…...

软考-系统可靠性原理

系统可靠性原理...

【Unity】【Amplify Shader Editor】ASE入门系列教程第二课 硬边溶解

黑色为0,白色为1 新建材质&#xff08;不受光照影响&#xff09; 拖入图片 设置 添加节点&#xff1a; 快捷键&#xff1a;K 组合通道&#xff1a;快捷键 V 完成图...

对神经网络理解的个人记录

对神经网络理解的个人记录 一、 神经网络为什么可以拟合函数、非线性函数二、 用向量表示特征(语音、文本、视频)。然后如何计算向量之间的相似度2.1 欧氏距离的计算2.2 点积运算2.3 余弦相似度计算一、 神经网络为什么可以拟合函数、非线性函数 第一个小短片:讲解神经网络为什…...

华为数通方向HCIP-DataCom H12-821题库(单选题:61-80)

第61题 关于 BGP 的Keepalive报文消息的描述,错误的是 A、Keepalive周期性的在两个BGP邻居之间发送 B、Keepalive报文主要用于对等路由器间的运行状态和链路的可用性确认 C、Keepalive 报文只包含一个BGP数据报头 D、缺省情况下,Keepalive 的时间间隔是180s 答案&#xff…...

Unity带有时效性的数据存储

Unity带有时效性的数据存储 引言 在Unity项目开发中&#xff0c;有时候会遇到带有时效性的数据存储&#xff0c;比如账号信息、token等&#xff0c;都是具有时效性的&#xff0c;这时候我们就需要在这些信息过期的时候将对应的信息作废。 实现 这个功能怎么实现呢&#xff…...

vue 子组件 emit传递事件和事件数据给父组件

1 子组件通过emit 函数 传递事件名init-complete 和 数据dateRange this.$emit(init-complete, dateRange) 2 父组件 创建方法 接收数据 handleInitComplete(dateRange) {} 3 父组件 创建的方法 和 子组件事件绑定 <component :is"currentComponent" :passOb…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...