算法训练营第五十天 | LeetCode 198 打家劫舍、LeetCode 213 打家劫舍II、LeetCode 337 打家劫舍III
LeetCode 198 打家劫舍
代码如下:
class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size() + 1, 0);dp[1] = nums[0];for (int i = 2; i <= nums.size(); i++) {dp[i] = max(dp[i - 1] ,dp[i - 2] + nums[i - 1]);}return dp[nums.size()];}
};
LeetCode 213 打家劫舍II
分情况进行讨论即可
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);}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 137 打家劫舍III
直接用简单版递归会超时
class Solution {public int innerRob(int state, TreeNode root) {if (root == null) return 0;if (state == 1) {return (innerRob(0, root.left) + innerRob(0, root.right));} else {return Math.max(root.val + innerRob(1, root.left) + innerRob(1, root.right), innerRob(0, root.left) + innerRob(0, root.right));}}public int rob(TreeNode root) {if (root == null) return 0;return Math.max(root.val + innerRob(1, root.left) + innerRob(1, root.right), innerRob(0, root.left) + innerRob(0, root.right));}
}
用哈希表记录下重复子问题就没问题了
class Solution {Map<TreeNode, Integer> choose = new HashMap<TreeNode, Integer>();Map<TreeNode, Integer> not_choose = new HashMap<TreeNode, Integer>();public void dfs (TreeNode root) {if (root == null) return;dfs(root.left);dfs(root.right);choose.put(root, root.val + not_choose.getOrDefault(root.left,0) + not_choose.getOrDefault(root.right,0));not_choose.put(root,Math.max(Math.max(choose.getOrDefault(root.left,0) + choose.getOrDefault(root.right,0), not_choose.getOrDefault(root.left,0) + not_choose.getOrDefault(root.right,0)),Math.max(choose.getOrDefault(root.left,0) + not_choose.getOrDefault(root.right,0), not_choose.getOrDefault(root.left,0) + choose.getOrDefault(root.right,0))));}public int rob(TreeNode root) {dfs(root);return Math.max(choose.getOrDefault(root,0), not_choose.getOrDefault(root,0));}
}
优化后代码如下:
class Solution {Map<TreeNode, Integer> choose = new HashMap<TreeNode, Integer>();Map<TreeNode, Integer> not_choose = new HashMap<TreeNode, Integer>();public void dfs (TreeNode root) {if (root == null) return;dfs(root.left);dfs(root.right);choose.put(root, root.val + not_choose.getOrDefault(root.left,0) + not_choose.getOrDefault(root.right,0));not_choose.put(root,Math.max(choose.getOrDefault(root.left,0), not_choose.getOrDefault(root.left,0)) + Math.max(choose.getOrDefault(root.right,0), not_choose.getOrDefault(root.right,0)));}public int rob(TreeNode root) {dfs(root);return Math.max(choose.getOrDefault(root,0), not_choose.getOrDefault(root,0));}
}
相关文章:
算法训练营第五十天 | LeetCode 198 打家劫舍、LeetCode 213 打家劫舍II、LeetCode 337 打家劫舍III
LeetCode 198 打家劫舍 代码如下: class Solution { public:int rob(vector<int>& nums) {vector<int> dp(nums.size() 1, 0);dp[1] nums[0];for (int i 2; i < nums.size(); i) {dp[i] max(dp[i - 1] ,dp[i - 2] nums[i - 1]);}return dp…...
linux学习:进程通信 管道
目录 例子1 父进程向子进程发送一条消息,子进程读取这条消息 例子2 mkfifo 函数创建一个命名管道 例子3 mkfifo 函数创建一个命名管道处理可能出现的错误 例子4 管道文件是否已存在 例子5 除了“文件已存在”进行处理 例子6 创建一个命名管道&…...
重大变化,2024软考!
根据官方发布的2024年度计算机技术与软件专业技术资格(水平)考试安排,2024年软考上、下半年开考科目有着巨大变化,我为大家整理了相关信息,大家可以看看! 🎯2024年上半年:5月25日&am…...
DRIVEN|15分的CNN+LightGBM怎么做特征分类,适用于转录组
说在前面 今天分享一篇做深度学习模型的文章,这是一篇软硬结合的研究,排除转换实体产品,我们做生信基础研究的可以学习模仿这个算法,适用且不局限于临床资料,转录组数据,GWAS数据。 今天给大家分享的一篇文…...
react 怎样配置ant design Pro 路由?
Ant Design Pro 是基于 umi 和 dva 的框架,umi 已经预置了路由功能,只需要在 config/router.config.js 中添加路由信息即可。 例如,假设你需要为 HelloWorld 组件创建一个路由,你可以将以下代码添加到 config/router.config.js 中…...
DBSCAN 算法【python,机器学习,算法】
DBSCAN 即 Density of Based Spatial Clustering of Applications with Noise,带噪声的基于空间密度聚类算法。 算法步骤: 初始化: 首先,为每个数据点分配一个初始聚类标签,这里设为0,表示该点尚未被分配…...
MySQL之查询性能优化(六)
查询性能优化 查询优化器 9.等值传播 如果两个列的值通过等式关联,那么MySQL能够把其中一个列的WHERE条件传递到另一列上。例如,我们看下面的查询: mysql> SELECT film.film_id FROM film-> INNER JOIN film_actor USING(film_id)-> WHERE f…...
生成树协议STP(Spanning Tree Protocol)
为了提高网络可靠性,交换网络中通常会使用冗余链路。然而,冗余链路会给交换网络带来环路风险,并导致广播风暴以及MAC地址表不稳定等问题,进而会影响到用户的通信质量。生成树协议STP(Spanning Tree Protocol࿰…...
03-3.1.1 栈的基本概念
👋 Hi, I’m Beast Cheng👀 I’m interested in photography, hiking, landscape…🌱 I’m currently learning python, javascript, kotlin…📫 How to reach me --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以订…...
排序算法集合
1. 冒泡排序 排序的过程分为多趟,在每一趟中,从前向后遍历数组的无序部分,通过交换相邻两数位置的方式,将无序元素中最大的元素移动到无序部分的末尾(第一趟中,将最大的元素移动到数组倒数第一的位置&…...
pdf文件太大如何变小,苹果电脑压缩pdf文件大小工具软件
压缩PDF文件是我们在日常办公和学习中经常会遇到的需求。PDF文件由于其跨平台、保持格式不变的特点,被广泛应用于各种场合。然而,有时候我们收到的PDF文件可能过大,不便于传输和存储,这时候就需要对PDF文件进行压缩。下面…...
vite项目打包,内存溢出
解决方案: "build1": "node --max-old-space-size8096 ./node_modules/vite/bin/vite.js build", 人工智能学习网站 https://chat.xutongbao.top...
Matlab解决施密特正交规范化矩阵(代码开源)
#最近在学习matlab,刚好和线代论文重合了 于是心血来潮用matlab建了一个模型来解决施密特正交规范化矩阵。 我们知道这个正交化矩阵挺公式化的,一般公式化的内容我们都可以用计算机来进行操作,节约我们人工的时间。 我们首先把矩阵导入进去…...
自养号测评助力:如何打造沃尔玛爆款?
沃尔玛,作为全球零售业的领军者,其平台为卖家们提供了一个巨大的商业舞台。然而,在这个竞争激烈的舞台上,如何迅速且有效地提升销量,成为了卖家们必须面对的重大挑战。 在探讨沃尔玛平台销量提升的策略时,我…...
C语言编译与链接
C语言编译与链接 目录 C语言编译与链接 一、概述 二、编译过程 三、链接过程...
电子电器架构 --- 智能座舱技术分类
电子电器架构 — 智能座舱技术分类 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,…...
提供操作日志、审计日志解决方案思路
操作日志 现在大部分公司一般使用SpringCloud这条技术栈,操作日志通过网关Gateway提供的Globalfilter统一拦截请求解析请求是比较好的选选择。 优点:相对于传统的过滤器、拦截器同步阻塞方案,SpringCloud Gateway使用的Webflux中的reactor-…...
选择富唯智能的可重构装配系统,就是选择了一个可靠的合作伙伴
在数字化、智能化的浪潮中,制造业正迎来一场前所未有的变革。而在这场变革中,富唯智能凭借其卓越的技术实力和创新能力,成为引领行业发展的领军企业。选择富唯智能的可重构装配系统,就是选择了一个可靠的合作伙伴,共同…...
echarts tooltip太多显示问题解决方案
思路:设置5个一换行 tooltip: {trigger: axis,confine:true,//限制tooltip在图表范围内展示// extraCssText: max-height:60%;overflow-y:scroll,//最大高度以及超出处理extraCssText: max-height:60%;overflow-y:scroll;white-space: normal;word-break: break-al…...
【control_manager】无法加载,gazebo_ros2_control 0.4.8,机械臂乱飞
删除URDF和SDRF文件中的特殊注释#, !,: xacro文件解析为字符串时出现报错 一开始疯狂报错Waiting for /controller_manager node to exist 1717585645.4673686 [spawner-2] [INFO] [1717585645.467015300] [spawner_joint_state_broadcaster]: Waiting for /con…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
