当前位置: 首页 > 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…...

保姆级教程:用串口和Telnet连接Hi3559/Hi3516开发板,5分钟搞定环境搭建

5分钟极速上手&#xff1a;Hi3559/Hi3516开发板串口与Telnet连接实战指南 刚拿到海思开发板时&#xff0c;许多开发者会被一堆陌生的接口和术语吓退。其实只要掌握几个关键步骤&#xff0c;从拆箱到建立稳定连接只需一根串口线和五分钟时间。本文将用最直白的语言&#xff0c;带…...

提升钱包开发效率:用快马AI一键生成imToken风格的高复用UI组件

提升钱包开发效率&#xff1a;用快马AI一键生成imToken风格的高复用UI组件 开发钱包类应用时&#xff0c;最让人头疼的就是那些重复性的UI组件和交互逻辑。每次新项目都要从零开始写资产卡片、交易记录列表、二维码弹窗这些基础组件&#xff0c;不仅耗时耗力&#xff0c;还容易…...

SDMatte抠图实战教程:玻璃/薄纱/羽毛一键去背景,保姆级Web部署指南

SDMatte抠图实战教程&#xff1a;玻璃/薄纱/羽毛一键去背景&#xff0c;保姆级Web部署指南 1. 为什么选择SDMatte进行专业抠图 在日常设计工作中&#xff0c;抠图是最基础也最耗时的环节之一。特别是遇到玻璃制品、薄纱材质、羽毛边缘这类复杂对象时&#xff0c;传统Photosho…...

Windows 11 下 3D Gaussian Splatting (3DGS) 环境配置与实战指南

1. Windows 11下的3DGS环境搭建全攻略 第一次接触3D Gaussian Splatting&#xff08;简称3DGS&#xff09;这个技术时&#xff0c;我完全被它惊艳到了。它能够从几张普通的照片重建出逼真的3D场景&#xff0c;而且渲染速度极快。不过说实话&#xff0c;在Windows 11上配置这个环…...

如何解决3D视频无法在普通设备播放的难题?VR-Reversal让转换更简单

如何解决3D视频无法在普通设备播放的难题&#xff1f;VR-Reversal让转换更简单 【免费下载链接】VR-reversal VR-Reversal - Player for conversion of 3D video to 2D with optional saving of head tracking data and rendering out of 2D copies. 项目地址: https://gitco…...

如何快速上手uesave-rs:虚幻引擎存档编辑的终极指南

如何快速上手uesave-rs&#xff1a;虚幻引擎存档编辑的终极指南 【免费下载链接】uesave 项目地址: https://gitcode.com/gh_mirrors/ue/uesave 还在为无法修改心爱游戏的存档而烦恼吗&#xff1f;想要自定义游戏体验却不知从何下手&#xff1f;uesave-rs这款强大的Rus…...

Python 装饰器实战:用@syntax 优雅地增强函数功能

# Python 装饰器实战&#xff1a;用syntax 优雅地增强函数功能## 什么是装饰器&#xff1f;装饰器&#xff08;Decorator&#xff09;是 Python 中的一种高级特性&#xff0c;它允许你在不修改原函数代码的情况下&#xff0c;动态地给函数添加功能。简单来说&#xff0c;装饰器…...

苹果内购订阅的“时间陷阱”:如何正确处理UTC与东八区的时间转换(附Java代码)

苹果订阅时间戳的时区陷阱&#xff1a;UTC与东八区转换的实战指南 1. 为什么时间戳处理如此重要&#xff1f; 在苹果应用内购&#xff08;IAP&#xff09;订阅系统中&#xff0c;时间戳处理看似简单&#xff0c;实则暗藏玄机。许多开发者都曾踩过这样的坑&#xff1a;用户明明购…...

RTX 4090D专属镜像应用场景:短视频MCN机构批量生成口播视频生产系统

RTX 4090D专属镜像应用场景&#xff1a;短视频MCN机构批量生成口播视频生产系统 1. 短视频行业的痛点与解决方案 短视频MCN机构每天面临的最大挑战之一&#xff0c;就是如何高效生产大量高质量的口播视频内容。传统制作流程通常需要&#xff1a; 租用专业摄影棚聘请主播录制…...

Keepalived+Nginx+Tomcat 高可用项目集成 MySQL 数据库全记录

前言在之前的文章中&#xff0c;我搭建了基于 KeepalivedNginxTomcat 的高可用 Web 架构&#xff0c;实现了入口 VIP 漂移和反向代理。但这套架构还缺少“数据层”——所有服务都是无状态的&#xff0c;不能持久化数据。为了让项目更完整&#xff0c;我决定加入 MySQL 数据库&a…...