43-设计问题-最小栈
原题链接:
198. 打家劫舍
题目描述:
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
数据范围:
1 <= nums.length <= 1000 <= nums[i] <= 400
测试样例:
示例 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 。
思路:二维动态规划
对于每一家而言,都有 偷了 和 没偷 这两种状态,所以可以用一个二维 dp 数组(共 2 行 n 列)来表示某一家是否被偷。顺序遍历原数组,模拟小偷从第一家偷到最后一家的过程。那么有 dp[0][i] 表示小偷走到索引为 i 的那一家,但是没偷他们家时获得的最大金额;相应的 dp[1][i] 表示小偷走到索引为 i 的那一家,并且偷了他们家时获得的最大金额。因为被偷的两家不能相邻,所以可以得到递推关系:dp[0][i] = max(dp[0][i-1], dp[1][i-1]),因为 dp[0][i] 表示没有偷这一家所以偷没偷前面的一家无所谓,返回二者中的最大值;dp[1][i] = dp[0][i-1] + nums[i],因为 dp[1][i] 表示偷了这一家所以前一家必定不能偷,只能是 dp[0][i-1] 但是又因为偷了当前这个一家收益还要增加 nums[i]。并且可以得到初始值分别为 dp[0][0] = 0 和 dp[1][0] = nums[0]。仔细思考一下发现不重复不遗漏,那么最终的结果就是小偷走到最后一家时的最大收益 max(dp[0][n-1], dp[1][n-1])。
代码:
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();int dp[2][n];dp[0][0] = 0, dp[1][0] = nums[0];for (int i = 1; i < n; i ++) {dp[0][i] = max(dp[0][i-1], dp[1][i-1]);dp[1][i] = dp[0][i-1] + nums[i];}return max(dp[0][n-1], dp[1][n-1]);}
};
复杂度:
时间复杂度:
遍历了一遍整个数组
时间复杂度为 O(N)
空间复杂度:
创建了一个辅助数组存储 dp 结果
空间复杂度为 O(N)
相关文章:
43-设计问题-最小栈
原题链接: 198. 打家劫舍 题目描述: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入&a…...
基于RK3588全高端智能终端机器人主板
一、小尺寸板型设计 该款主板为小型板,尺寸仅为125*85mm,更小更紧凑,可完美适应各类高端智能自助终端; 二、八核高端处理器 采用RK3588S八核64位处理器,8nm LP制程,主频最高达2.4GHz,搭载Andr…...
穿越风波,“长红”的直播电商依然扎根产业和消费者
当消费者将最后一个快递拿进家门,2023年的双11也就落下了帷幕。相较于往年组队、拼单的玩法,如今最受欢迎的双11 流程,或许已经变成点进自己心仪主播、店铺的直播间,翻阅最新的产品清单,从中选择购物目标,在…...
LLM大模型 (chatgpt) 在搜索和推荐上的应用
目录 1 大模型在搜索的应用1.1 召回1.1.1 倒排索引1.1.2 倒排索引存在的问题1.1.3 大模型在搜索召回的应用 (实体倒排索引) 1.2 排序1.2.1 大模型在搜索排序应用(融入LLM实体排序) 2 大模型在推荐的应用2.1 学术界关于大模型在推荐的研究2.2 …...
中国净初级生产力年度合成产品NPP(MYD17A3H.006)
中国净初级生产力年度合成产品NPP(MYD17A3H.006)由航天宏图实验室提供,根据NASA MODIS数据(MYD17A3H.006)通过航天宏图 Smoother计算得到的平滑后NPP产品,解决了影像云雾覆盖、像元异常值等问题。对处理后的…...
GitHub如何删除仓库
GitHub如何删除仓库 删除方法第一步第二步第三步 删除方法 第一步 在仓库的界面选择Settings 第二步 选择General,页面拉到最后。 第三步 删除仓库。...
漫谈广告机制设计 | 万剑归宗:聊聊广告机制设计与收入提升的秘密(3)
书接上文漫谈广告机制设计 | 万剑归宗:聊聊广告机制设计与收入提升的秘密(2),我们聊到囚徒困境是完全信息静态博弈,参与人存在占优策略,最终达到占优均衡,并且是对称占优均衡。接下来我们继续…...
安装系统时无raid驱动处理办法
场景描述 安装系统时可以进入安装界面,但是无法识别到硬盘,查看服务器硬件均无异常且从bios或者raid配置界面中能正常看到raid信息及硬盘信息,运行lspci 命令查看到服务器有raid卡,但是未加载驱动。 获取驱动程序模块 查看raid…...
ForkLift:macOS文件管理器/FTP客户端
ForkLift 是一款macOS下双窗口的文件管理器,可以代替本地的访达。ForkLift同时具备连接Ftp、SFtp、WebDav以及云服务器。 ForkLift还具备访达不具备的小功能,比如从文件夹位置打开终端,显示隐藏文件,制作替换等功能。ForkLift 是一…...
信息系统项目管理师 第四版 第20章 高级项目管理
1.项目集管理 1.1.项目集管理标准 1.2.项目集管理角色和职责 1.3.项目集管理绩效域 2.项目组合管理 2.1.项目组合管理标准 2.2.项目组合管理角色和职责 2.3.项目组合管理绩效域 3.组织级项目管理 3.1.组织级项目管理标准 3.2.业务价值与业务评估 3.3.OPM框架要素 3…...
Apache Pulsar 技术系列 - 基于 Pulsar 的海量 DB 数据采集和分拣
导语 Apache Pulsar 是一个多租户、高性能的服务间消息传输解决方案,支持多租户、低延时、读写分离、跨地域复制、快速扩容、灵活容错等特性。本文是 Pulsar 技术系列中的一篇,主要介绍 Pulsar 在海量DB Binlog 增量数据采集、分拣场景下的应用。 前言…...
HDFS、MapReduce原理--学习笔记
1.Hadoop框架 1.1框架与Hadoop架构简介 (1)广义解释 从广义上来说,随着大数据开发技术的快速发展与逐步成熟,在行业里,Hadoop可以泛指为:Hadoop生态圈。 也就是说,Hadoop指的是大数据生态圈整…...
PC端使子组件的弹框关闭
子组件 <template><el-dialog title"新增部门" :visible"showDialog" close"close"> </el-dialog> </template> <script> export default {props: {showDialog: {type: Boolean,default: false,},},data() {retu…...
PHPStorm PHP-CS-Fixer
我用的是brew安装: brew install php-cs-fixer phpstorm配置: setting搜索fixer 指定安装php-cs-fixer的目录: https://github.com/PHP-CS-Fixer/PHP-CS-Fixer/blob/master/doc/installation.rst 图文详解PHPStorm实现自动执行代码格式化-…...
SpringBoot中日志的使用log4j
SpringBoot中日志的使用log4j 项目中日志系统是必不可少的,目前比较流行的日志框架有 log4j、logback 等,这两个框架的作者是同一个 人,Logback 旨在作为流行的 log4j 项目的后续版本,从而恢复 log4j 离开的位置。 另外 slf4j(…...
迭代器与生成器
章节目录: 一、迭代器1.1 相关概述1.2 基本使用1.3 自定义迭代器 二、生成器2.1 相关概述2.2 基本使用2.3 三种应用场景 三、yield 和 class 定义的迭代器对比四、结束语 一、迭代器 1.1 相关概述 迭代是 Python 最强大的功能之一,是访问集合元素的一种…...
适用于 Windows 的 10 个最佳视频转换器:快速转换高清视频
您是否遇到过由于格式不兼容而无法在您的设备上播放视频或电影的情况?您想随意播放从您的相机、GoPro 导入的视频,还是以最合适的格式将它们上传到媒体网站?您的房间里是否有一堆 DVD 光盘,想将它们转换为数字格式以便于播放&…...
分布式锁的概念、应用场景、实现方式和优缺点对比
一:什么是分布式锁 分布式锁是一种用于协调分布式系统中多个节点对共享资源的访问的机制。在分布式系统中,由于多个节点的并发执行,可能会导致对共享资源的竞争,而分布式锁的目的就是确保在任何时刻,只有一个节点能够持…...
Linux:常见指令
个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》《C》 文章目录 前言一、常见指令ls指令pwd指令cd指令touch指令mkdir指令rmdir指令rm指令man指令cp指令mv指令cat指令tac指令echo指令more指令less指令head指令tail指令date显示Cal指令find指令gr…...
大数据基础设施搭建 - ZooKeeper
文章目录 一、上传压缩包二、解压压缩包三、本机安装3.1 修改配置文件3.1.1 创建ZooKeeper数据存储目录3.1.2 修改配置文件名3.1.2 修改配置文件内容 3.3 启动/停止服务端3.4 测试(1)启动客户端(2)测试客户端操作 四、集群安装4.1…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
