代码随想录第48天 | 198. 打家劫舍、213. 打家劫舍II、337. 打家劫舍III
198. 打家劫舍
当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。
递归五部曲:
- dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。
- 决定dp[i]的因素就是第i房间偷还是不偷。
- 如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ,即:第i-1房一定是不考虑的,找出 下标i-2(包括i-2)以内的房屋,最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
- 如果不偷第i房间,那么dp[i] = dp[i - 1],即考 虑i-1房
然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
- 递推公式的基础就是dp[0] 和 dp[1]。从dp[i]的定义上来讲,dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1])
- dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从2开始从前到后遍历
/*** @param {number[]} nums* @return {number}*/
var rob = function (nums) {const len = nums.lengthconst dp = [nums[0], Math.max(nums[0], nums[1])]for (let i = 2; i < len; i++) {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])}return dp[len - 1]
};
213. 打家劫舍II
成环的话主要有如下三种情况:
- 考虑不包含首尾元素
- 考虑包含首元素,不包含尾元素
- 考虑包含首元素,不包含尾元素
情况二 和 情况三 都包含了情况一了,所以只考虑情况二和情况三就可以了。剩下的就和普通的打家劫舍一样了。
/*** @param {number[]} nums* @return {number}*/
var rob = function (nums) {const n = nums.lengthif (n === 0) return 0if (n === 1) return nums[0]const result1 = robRange(nums, 0, n - 2)const result2 = robRange(nums, 1, n - 1)return Math.max(result1, result2)
};const robRange = (nums, start, end) => {if (end === start) return nums[start]const dp = new Array(nums.length).fill(0)dp[start] = nums[start]dp[start + 1] = Math.max(nums[start], nums[start + 1])for (let i = start + 2; i <= end; i++) {dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])}return dp[end]
}
337. 打家劫舍III
使用一个长度为2的数组,记录当前节点偷与不偷所得到的的最大金钱。
递归三部曲:
- 确定递归函数的参数和返回值
要求一个节点 偷与不偷的两个状态所得到的金钱,那么返回值就是一个长度为2的数组。
dp数组(dp table)以及下标的含义:下标为0记录不偷该节点所得到的的最大金钱,下标为1记录偷该节点所得到的的最大金钱。 - 确定终止条件
在遍历的过程中,如果遇到空节点的话,很明显,无论偷还是不偷都是0,所以就返回 - 确定遍历顺序
首先明确的是使用后序遍历。 因为要通过递归函数的返回值来做下一步计算。
通过递归左节点,得到左节点偷与不偷的金钱。
通过递归右节点,得到右节点偷与不偷的金钱。 - 确定单层递归逻辑
如果是偷当前节点,那么左右孩子就不能偷;
如果不偷当前节点,那么左右孩子就可以偷,至于到底偷不偷一定是选一个最大的 - 举例推导dp数组
最后头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var rob = function (root) {const postOrder = node => {// 递归出口if (!node) return [0, 0];// 遍历左子树const left = postOrder(node.left);// 遍历右子树const right = postOrder(node.right);// 不偷当前节点,左右子节点都可以偷或不偷,取最大值const DoNot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);// 偷当前节点,左右子节点只能不偷const Do = node.val + left[0] + right[0];// [不偷,偷]return [DoNot, Do];};const res = postOrder(root);// 返回最大值return Math.max(...res);
};
相关文章:
代码随想录第48天 | 198. 打家劫舍、213. 打家劫舍II、337. 打家劫舍III
198. 打家劫舍 当前房屋偷与不偷取决于 前一个房屋和前两个房屋是否被偷了。 递归五部曲: dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。决定dp[i]的因素就是第i房间偷还是不偷。 如果偷第i房间&…...
【LeetCode】按摩师
按摩师 题目描述算法分析编程代码 链接: 按摩师 题目描述 算法分析 编程代码 class Solution { public:int massage(vector<int>& nums) {int n nums.size();if(n 0) return 0;vector<int> f(n);auto g f;f[0] nums[0];for(int i 1;i<n;i){f[i] g[i…...
国际腾讯云账号云核算概述!!
云核算概述 维基百科界说:云核算是一种依据互联网的新型核算方法,经过互联网上异构、自治的服务为个人和企业供给按需即取的核算。 云核算描绘的一起特征:云是一种按需运用的服务,运用者只重视服务本身。 云核算作为IT服务形式&am…...
.NET 6.0 重启 IIS 进程池
在 .NET 6.0 中,你可以使用 Microsoft.Web.Administration 命名空间提供的 API 来管理 IIS 进程池并实现重启操作。以下是一个示例代码,展示如何使用 .NET 6.0 中的 Microsoft.Web.Administration 来重启 IIS 进程池: using Microsoft.Web.A…...
一位心理学教师对ChatGPT的看法,提到了正确地使用它的几个要点
在没有自主学习能力和有自主学习能力的两类学生中,ChatGPT的出现,会加大他们在知识学习及思维发展上的鸿沟。爱学习的人会因为AI变得更好…… 从2022年年底起,ChatGPT的技术突破使人类终于进入了一个AI被广泛应用在工作、学习、生活的时代。…...
认识Node.js及三个模块
文章目录 1.初识 Node.js1.1 什么是 Node.js1.2 Node.js 中的 JavaScript 运行环境1.3 Node.js 可以做什么1.4 Node.js 环境的安装1.4.1 区分 LTS 版本和 Current 版本的不同1.4.2 查看已安装的 Node.js 的版本号1.4.3 什么是终端1.4.4 终端中的快捷键 1.5 在 Node.js 环境中执…...
49 | 公司销售数据分析
公司销售数据分析报告 本数据是2012~2014年间一家生产体育类产品的全球销售订单数据,分别按时间、产品类别、销售国家统计产品销售情况,分析销售额和利润额统计各产品市场占有份额,为下一步生产计划提供有价值的建议。 数据大小:88475 行, 11 列 Retailer country销售国…...
Android 项目导入高德SDK初次上手
文章目录 一、前置知识:二、学习目标三、学习资料四、操作过程1、创建空项目2、高德 SDK 环境接入2.1 获取高德 key2.2下载 SDK 并导入2.2.1、下载SDK 文件2.2.2、SDK 导入项目2.2.3、清单文件配置2.2.4、隐私权限 3、显示地图 一、前置知识: 1、Java 基…...
生成树协议用来解决网络风暴的问题?(第三十二课)
生成树协议用来解决网络风暴的问题?(第三十二课) 一 STP RSTP MSTP 介绍 STP(Spanning Tree Protocol)、RSTP(Rapid Spanning Tree Protocol)和MSTP(Multiple Spanning Tree Protocol)都是用于网络中避免环路的协议。 STP是最初的协议,它通过将某些端口阻塞来防止…...
git分支操作
Git分支的操作 1.1 Git分支简介 Git分支是由指针管理起来的,所以创建、切换、合并、删除分支都非常快,非常适合大型项目的开发。 在分支上做开发,调试好了后再合并到主分支。那么每个人开发模块式都不会影响到别人。 分支使用策略…...
【基础学习笔记 enum】TypeScript 中的 enum 枚举类型介绍
因为之前网上查好多博客都是只说最基础的,所以这里记录一下,最基础的放在最后面。 这里重点要记录的是枚举成员的值可以是字符串(字符串枚举,因为网上大部分只介绍常数枚举),需要注意的一点是,…...
SpringBoot中间件使用之EventBus、Metric、CommandLineRunner
1、EventBus 使用EventBus 事件总线的方式可以实现消息的发布/订阅功能,EventBus是一个轻量级的消息服务组件,适用于Android和Java。 // 1.注册事件通过 EventBus.getDefault().register(); // 2.发布事件 EventBus.getDefault().post(“事件内容”); …...
ffmpeg命令行是如何打开vf_scale滤镜的
前言 在ffmpeg命令行中,ffmpeg -i test -pix_fmt rgb24 test.rgb,会自动打开ff_vf_scale滤镜,本章主要追踪这个流程。 通过gdb可以发现其基本调用栈如下: 可以看到,query_formats()中创建的v…...
【Vue3】自动引入插件-`unplugin-auto-import`
Vue3自动引入插件-unplugin-auto-import,不必再手动 import 。 自动导入 api 按需为 Vite, Webpack, Rspack, Rollup 和 esbuild 。支持TypeScript。由unplugin驱动。 插件安装:unplugin-auto-import 配置vite.config.ts(配置完后需要重启…...
每日温度(力扣)单调栈 JAVA
给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。 示例 1: 输入: temperatur…...
博客项目(Spring Boot)
1.需求分析 注册功能(添加用户操纵)登录功能(查询操作)我的文章列表页(查询我的文章|文章修改|文章详情|文章删除)博客编辑页(添加文章操作)所有人博客列表(带分页功能)…...
修改Jenkins存储目录
注意:在Jenkins运行时是不能更改的. 请先将Jenkins停止运行。 1、windows环境下更改JENKINS的主目录 Windows环境中,Jenkins主目录默认在C:Documents and SettingsAAA.jenkins 。可以通过设置环境变量来修改,例如: JENKINS_HOME…...
数据结构【第4章】——栈与队列
队列是只允许在一端进行插入操作、而在另-端进行删除操作的线性表。 栈 栈与队列:栈是限定仅在表尾进行插入和删除操作的线性表。 我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)&…...
android webview 显示灰度网页
要在WebView中显示网页灰度显示,您可以通过以下步骤操作: 在您的布局文件中添加WebView组件: <WebViewandroid:id"id/webview"android:layout_width"match_parent"android:layout_height"match_parent" /…...
Linux操作系统的基础使用技能的训练大纲(超级详细版本适合于初学者)
RHCE红帽认证工程师课程对应考试课 程 纲 要 第一部分 网络基础 RH033RH302 Linux基础: 1) 在bashshell命令行模式下运行基本的Linux命令 2) 从命令行及GNOME界面启动应用程序 3) 使用及配置Xwindow系统及GNOME桌面环境 4) 使用GNOME GUI应用程序完成一般的工作 5) 了解Linu…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...
STM32标准库-ADC数模转换器
文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”:输入模块(GPIO、温度、V_REFINT)1.4.2 信号 “调度站”:多路开关1.4.3 信号 “加工厂”:ADC 转换器(规则组 注入…...
python打卡第47天
昨天代码中注意力热图的部分顺移至今天 知识点回顾: 热力图 作业:对比不同卷积层热图可视化的结果 def visualize_attention_map(model, test_loader, device, class_names, num_samples3):"""可视化模型的注意力热力图,展示模…...
