【代码随想录训练营第42期 Day39打卡 - 打家劫舍问题 - LeetCode 198.打家劫舍 213.打家劫舍II 337.打家劫舍III

news/2024/9/18 15:05:23/ 标签: leetcode, 算法, 打家劫舍问题

目录

一、做题心得

二、题目与题解

题目一:198.打家劫舍

题目链接

题解:动态规划

题目二:213.打家劫舍II

题目链接

题解:动态规划

 题目三:337.打家劫舍III

题目链接

题解:动态规划

三、小结


一、做题心得

今天是打家劫舍的一天,来到了动态规划章节的Part7。打家劫舍问题是动态规划算法很经典的一个应用,今天将从三道题目对其进行探讨。

话不多说,直接开始今天的内容。

二、题目与题解

题目一:198.打家劫舍

题目链接

198. 打家劫舍 - 力扣(LeetCode)

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

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

示例 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 <= nums.length <= 100
  • 0 <= nums[i] <= 400
题解:动态规划

这是打家劫舍问题最经典的应用,我们无法打劫相邻的两个房屋,这里需要注意的是:偷取的房屋之间不一定是只隔一间房屋 -- 这一点容易出错。

对于当前房屋而言,偷与不偷取决于前一个房屋和前两个房屋是否被偷,这就说明前边状态会对当前状态造成影响 -- 这正符合动态规划的思想。

首先就是初始化:这里由于当前房屋偷与不偷受到前两天的影响,故初始化至少需要最初的两个房屋。

状态方程 -- 考虑当前状态偷与不偷:dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

        1.前者:不偷窃第 i 间房屋,偷窃总金额为前 i−1 间房屋的最高总金额 -- 注意:这并不表示就一定要偷第 i-1 间房屋

        2.后者:偷窃第 i 间房屋,那么就不能偷窃第 i−1 间房屋,偷窃总金额为前 i−2 间房屋的最高总金额与第 i 间房屋的金额之和

代码如下:

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if (n == 0)     return 0;if (n == 1)     return nums[0];vector<int> dp(n, 0);       //dp[i]表示下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i](即0 - i)dp[0] = nums[0];            //初始化dp[0]与dp[1]dp[1] = max(nums[0], nums[1]);for (int i = 2; i < n; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);    //第i个房间偷还是不偷--取较大值}return dp[n - 1];       //房间数组下标范围:0 - n-1}
};

题目二:213.打家劫舍II

题目链接

213. 打家劫舍 II - 力扣(LeetCode)

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

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

示例 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 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
题解:动态规划

这道题在上一道题的基础上将房屋形成了一个环--首尾相接的环。

那么整体上思路就是一样的,唯一的不同就是我们必须保证首尾两个房屋最多只能选择一个去偷。

关键:通过自定义函数将围成环的打家劫舍问题转换为不围成环的打家劫舍问题(上一道题),得到这两种情况的结果:

    1.考虑头元素,不考虑尾元素:ans1 (注意:考虑不代表一定会偷

    2.考虑尾元素,不考虑头元素:ans2

再取两者较大值即可。

这里需要注意的是:头尾元素都不取的情况有被以上两种情况的任一情况包含在内

代码如下:

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if (n == 0)   return 0;         //先考虑特殊情况--没有房屋或者只有一个房屋if (n == 1)   return nums[0];int ans1 = robRange(nums, 0, n - 2);       //考虑头元素,不考虑尾元素int ans2 = robRange(nums, 1, n - 1);       //考虑尾元素,不考虑头元素return max(ans1, ans2);}/*  198.打家劫舍的逻辑  */int robRange(vector<int>& nums, int start, int end) {           //自定义函数--不围成一圈的打家劫舍:start -- endint n = nums.size();if (end == start)       return nums[start];vector<int> dp(n);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];}
};

 题目三:337.打家劫舍III

题目链接

337. 打家劫舍 III - 力扣(LeetCode)

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

除了 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

提示:

  • 树的节点数在 [1, 104] 范围内
  • 0 <= Node.val <= 104
题解:动态规划

这是动态规划在树的应用--树形dp--树形dp就是在树上进行递归公式的推导

题目思路很清晰,就是将打劫问题转移到了树上边来实现。

一开始,感觉很容易想到层序遍历,但是层数过多的情况,会很难判断,而且复杂度较高,行不通。再考虑递归遍历,我们要得到盗取的最大金额,需要得到有返回值的结果--首先想到后序遍历。通过动态规划实现这个问题,我们需要先得到左右节点的值,才能计算当前节点偷与不偷的结果(因为直接相连的房屋不可都进行盗取),这就引出了左右根的遍历方式--很显然,后序遍历是可行的。

如何用后序遍历实现呢?这里我们直接看灵神的的代码,通过dfs函数,通过后序遍历遍历了整棵树,再得出盗取或者不盗取当前节点能得到的最大金额--注意:这里采用pair存储这两种情况的结果,可以降低时间复杂度。

代码表示:rob:偷当前节点       rob_not:不偷当前节点

l_rob;偷左子结点       r_rob:偷右子节点

代码如下:

class Solution {
public:pair<int, int> dfs(TreeNode* cur) {     //pair类型函数:第一个元素表示偷当前节点所能得到的最大金额,第二个元素表示不偷时if(cur == nullptr) {       //当前节点为空,那么无论偷不偷这个“空节点”,结果都是0 return {0, 0};}/*   后序遍历--左右根   */auto [l_rob, l_not_rob] = dfs(cur -> left);     //左--递归遍历左子树auto [r_rob, r_not_rob] = dfs(cur -> right);    //右--递归遍历右子树int rob = l_not_rob + r_not_rob + cur -> val;       //偷当前节点时,左右子节点都不能偷int rob_not = max(l_not_rob, l_rob) + max(r_not_rob, r_rob);    //不偷当前节点,则可以偷也可以不偷左右子节点,分别取左右子树在两种状态下的较大值相加 -- 注意:在这里左右子树是分开考虑的return {rob, rob_not};}int rob(TreeNode* root) {auto [root_rob, root_not_rob] = dfs(root);      //调用dfs函数计算整棵树偷与不偷的最大金额,并返回二者中的较大值return max(root_rob, root_not_rob);}
};

三、小结

今天的打卡到此也就结束了,感觉树的遍历这一块的内容还存在着一些欠缺,后边继续加油。


http://www.ppmy.cn/news/1517001.html

相关文章

通过React实现萤石摄像头rtsp地址格式的视频流的web展示

首先&#xff0c;我们需要拿到rtsp格式的流地址&#xff08;rtsp://admin:[password][ip]&#xff09;&#xff0c;其中 password:设备底下的6位数验证码 ip:设备的ipv4地址 这里拿到ip的方式可以直连网线和绑定wifi两种方式 然后下载PC端的萤石工作室&#xff08;下载中心…

五、Centos7-安装Jenkins

目录 一、基础环境准备 1.安装JDK 2.安装Tomcat 二、安装Jenkins 1.配置Jenkins插件镜像源 2.问题&#xff1a;进入manager jenkins页面报错 3.配置Git 4.配置jdk 三、重新安装Jenkins 四、另一种Centos安装jenkins的方式--最终可用版 克隆了一个base的虚拟机&#x…

UnrealEngine学习(01):安装虚幻引擎

1. 下载安装 Epic Games 目前下载UE引擎需要先下载Epic Games&#xff0c;官网为我们提供了下载路径&#xff1a; https://www.unrealengine.com/zh-CN/downloadhttps://www.unrealengine.com/zh-CN/download 我们点击图中步骤一即可进行下载。 注释&#xff1a;Unreal Engi…

未初始化的变量

学习C语言局部变量&#xff0c;经常听到这个说法。为什么局部变量默认是未初始化的&#xff1f;解释它需要理解程序结构和栈操作。 栈内存 C/C函数的局部变量保存在栈&#xff0c;栈可以认为是操作系统为了“加速”程序运行给线程配置了一块临时使用的内存区域&#xff0c;如果…

Spring Boot 框架中配置文件 application.properties 当中的所有配置大全

Spring Boot 框架中配置文件 application.properties 当中的所有配置大全 &#xff03;SPRING CONFIG&#xff08;ConfigFileApplicationListener&#xff09; spring.config.name &#xff03;配置文件名&#xff08;默认 为 application &#xff09; spring.config.lo…

一个干净的python项目(没连数据库啥的)

希望你们写代码有用&#xff08;直接可以拿来用&#xff0c;我只要您的一个关注和赞赞&#xff09; #用户数据 user1{"用户名":"aaa","密码":"123","姓名":"热孜娅","类型":"客户"} user2{&q…

Python 爬虫框架

Python 中有许多强大且主流的爬虫框架&#xff0c;这些框架提供了更高级的功能&#xff0c;使得开发和维护爬虫变得更加容易。以下是一些常用的爬虫框架&#xff1a; 1. Scrapy - 简介: Scrapy 是 Python 最流行的爬虫框架之一&#xff0c;设计用于快速、高效地从网站中提取…

【Rust光年纪】文本分析利器:探索Rust语言的多功能文本处理库

从情感分析到关键词提取&#xff1a;Rust语言文本分析库详解 前言 随着自然语言处理技术的不断发展&#xff0c;对各种文本数据进行分析和处理的需求也在不断增加。本文将介绍一些用于Rust语言的文本分析和处理库&#xff0c;包括情感分析、自然语言处理、中文转换、语言检查…

SQL,给连续的行加上标识序号

postgresql 数据库的表 tmp 有 2 个分组字段&#xff0c;source_id 和 event_user&#xff0c;将该表按 source_id 分组&#xff0c;组内按 event_date 排序后&#xff0c;event_user 相同的值会形成有序的小组&#xff1a; idsource_idevent_userevent_date11A05-03-201421A0…

DSB调制与解调仿真实验

一、实验目的&#xff1a; 熟悉使用SystemView软件&#xff0c;了解各部分功能模块的操作和使用方法。 通过实验进一步观察、了解模拟信号DSB调制、解调原理。 掌握DSB调制信号的主要性能指标。 比较、理解DSB调制的相干解调原理。 二、实验器材&#xff1a; 装有SystemV…

spring security怎么生成JWT返回前端,以及怎么自定义JWT认证过滤器

怎么生成JWT返回前端 1.先写一个类,里面含有jwt的生成解析验证过期时间的方法 package com.lzy.util;import io.jsonwebtoken.*; import lombok.Data; import org.springframework.boot.context.properties.ConfigurationProperties; import org.springframework.stereotype.…

黑神话悟空用什么编程语言

《黑神话&#xff1a;悟空》作为一款备受瞩目的国产单机动作游戏&#xff0c;其背后的开发涉及了多种编程语言和技术。根据公开信息和游戏开发行业的普遍做法&#xff0c;可以推测该游戏主要使用了以下几种编程语言&#xff1a; C&#xff1a; 核心编程语言&#xff1a;作为《黑…

从行为面试问题(behavioral questions)看中美程序员差异。

中美程序员在职场中的工作状态和职能、福利等有很大区别&#xff0c;从面试中的BQ轮就可见一斑。 中美程序员的面试轮差异&#xff1f; 国内的面试轮在不同公司间差异很大&#xff0c;但总体的问题类型包含笔试面试&#xff08;算法题、概念题、项目深挖、职业目标、职场文化…

【刷题笔记】leetCode448找到缺失的数

常规解法 public List<Integer> findDisappearedNumbers(int[] nums) {HashMap<Integer,Integer> numMap new HashMap<>();for (int i 0;i<nums.length;i){if (numMap.get(nums[i]) null){numMap.put(nums[i],i);}}List<Integer> result new A…

物联网关创业之路:从梦想到现实

在物联网大潮涌动的时代&#xff0c;李明看到了无限的机遇。他一直对科技充满热情&#xff0c;坚信物联网将改变人们的生活和工作方式。各类设备 IoT 的兴起&#xff0c;让他意识到一个强大的物联网关对于实现设备互联和数据传输的重要性。 李明决定投身于物联网关的设计开发创…

Apache Druid日志实时分析

业务分析 ​ 秒杀业务中&#xff0c;通常会有很多用户同时蜂拥而上去抢购热卖商品&#xff0c;经常会出现抢购人数远大于商品库存。其实在秒杀过程中&#xff0c;热卖商品并不多&#xff0c;几乎只占1%&#xff0c;而99%的流量都源自热卖商品&#xff0c;很有可能因为这1%的热…

Stream DATA From openai GPT-3 API using php

题意&#xff1a;“使用 PHP 从 OpenAI GPT-3 API 流式传输数据” 问题背景&#xff1a; Im having trouble with the OpenAI API, Basically what Im trying to do is stream each data node that is streamed back from the openai API response and output each data node …

综合评价 | 基于层次-熵权-变异系数-正态云组合法的综合评价模型(Matlab)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 综合评价 | 基于层次-熵权-变异系数-正态云组合法的综合评价模型&#xff08;Matlab&#xff09; AHP层次分析法是一种解决多目标复杂问题的定性和定量相结合进行计算决策权重的研究方法。该方法将定量分析与定性分析…

Qt:玩转QPainter序列一

前言 最近想潜心研究一下QPainter这个类&#xff0c;最好把QPainter所有的函数都敲一遍&#xff0c;特地记录一下。 在说QPainter之前我们需要了解两个非常重要的东西 第一个坐标系 我用两张图来表示 代码实操的结果 更加详细的坐标系内容请看我的另一篇博客 第二个是有…

VCTP(Visual Chain-of-Thought Prompting for Knowledge-Based Visual Reasoning)论文

目录 摘要介绍相关工作方法总体模型细节 实验 摘要 知识型视觉推理仍然是一个艰巨的任务&#xff0c;因为它不仅要求机器从视觉场景中解释概念和关系&#xff0c;而且还需要将它们与外部世界知识联系起来&#xff0c;对开放世界问题进行推理链。然而&#xff0c;以前的工作将视…