算法训练营第五十天 | 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…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
职坐标物联网全栈开发全流程解析
物联网全栈开发涵盖从物理设备到上层应用的完整技术链路,其核心流程可归纳为四大模块:感知层数据采集、网络层协议交互、平台层资源管理及应用层功能实现。每个模块的技术选型与实现方式直接影响系统性能与扩展性,例如传感器选型需平衡精度与…...
