当前位置: 首页 > news >正文

43-设计问题-最小栈

原题链接:

198. 打家劫舍

题目描述:

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

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

数据范围: 

  • 1 <= nums.length <= 100
  • 0 <= 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-设计问题-最小栈

原题链接&#xff1a; 198. 打家劫舍 题目描述&#xff1a; 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入&a…...

基于RK3588全高端智能终端机器人主板

一、小尺寸板型设计 该款主板为小型板&#xff0c;尺寸仅为125*85mm&#xff0c;更小更紧凑&#xff0c;可完美适应各类高端智能自助终端&#xff1b; 二、八核高端处理器 采用RK3588S八核64位处理器&#xff0c;8nm LP制程&#xff0c;主频最高达2.4GHz&#xff0c;搭载Andr…...

穿越风波,“长红”的直播电商依然扎根产业和消费者

当消费者将最后一个快递拿进家门&#xff0c;2023年的双11也就落下了帷幕。相较于往年组队、拼单的玩法&#xff0c;如今最受欢迎的双11 流程&#xff0c;或许已经变成点进自己心仪主播、店铺的直播间&#xff0c;翻阅最新的产品清单&#xff0c;从中选择购物目标&#xff0c;在…...

LLM大模型 (chatgpt) 在搜索和推荐上的应用

目录 1 大模型在搜索的应用1.1 召回1.1.1 倒排索引1.1.2 倒排索引存在的问题1.1.3 大模型在搜索召回的应用 (实体倒排索引&#xff09; 1.2 排序1.2.1 大模型在搜索排序应用&#xff08;融入LLM实体排序&#xff09; 2 大模型在推荐的应用2.1 学术界关于大模型在推荐的研究2.2 …...

中国净初级生产力年度合成产品NPP(MYD17A3H.006)

中国净初级生产力年度合成产品NPP&#xff08;MYD17A3H.006&#xff09;由航天宏图实验室提供&#xff0c;根据NASA MODIS数据&#xff08;MYD17A3H.006&#xff09;通过航天宏图 Smoother计算得到的平滑后NPP产品&#xff0c;解决了影像云雾覆盖、像元异常值等问题。对处理后的…...

GitHub如何删除仓库

GitHub如何删除仓库 删除方法第一步第二步第三步 删除方法 第一步 在仓库的界面选择Settings 第二步 选择General,页面拉到最后。 第三步 删除仓库。...

漫谈广告机制设计 | 万剑归宗:聊聊广告机制设计与收入提升的秘密(3)

​书接上文漫谈广告机制设计 | 万剑归宗&#xff1a;聊聊广告机制设计与收入提升的秘密&#xff08;2&#xff09;&#xff0c;我们聊到囚徒困境是完全信息静态博弈&#xff0c;参与人存在占优策略&#xff0c;最终达到占优均衡&#xff0c;并且是对称占优均衡。接下来我们继续…...

安装系统时无raid驱动处理办法

场景描述 安装系统时可以进入安装界面&#xff0c;但是无法识别到硬盘&#xff0c;查看服务器硬件均无异常且从bios或者raid配置界面中能正常看到raid信息及硬盘信息&#xff0c;运行lspci 命令查看到服务器有raid卡&#xff0c;但是未加载驱动。 获取驱动程序模块 查看raid…...

ForkLift:macOS文件管理器/FTP客户端

ForkLift 是一款macOS下双窗口的文件管理器&#xff0c;可以代替本地的访达。ForkLift同时具备连接Ftp、SFtp、WebDav以及云服务器。 ForkLift还具备访达不具备的小功能&#xff0c;比如从文件夹位置打开终端&#xff0c;显示隐藏文件&#xff0c;制作替换等功能。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 是一个多租户、高性能的服务间消息传输解决方案&#xff0c;支持多租户、低延时、读写分离、跨地域复制、快速扩容、灵活容错等特性。本文是 Pulsar 技术系列中的一篇&#xff0c;主要介绍 Pulsar 在海量DB Binlog 增量数据采集、分拣场景下的应用。 前言…...

HDFS、MapReduce原理--学习笔记

1.Hadoop框架 1.1框架与Hadoop架构简介 &#xff08;1&#xff09;广义解释 从广义上来说&#xff0c;随着大数据开发技术的快速发展与逐步成熟&#xff0c;在行业里&#xff0c;Hadoop可以泛指为&#xff1a;Hadoop生态圈。 也就是说&#xff0c;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安装&#xff1a; brew install php-cs-fixer phpstorm配置&#xff1a; setting搜索fixer 指定安装php-cs-fixer的目录&#xff1a; https://github.com/PHP-CS-Fixer/PHP-CS-Fixer/blob/master/doc/installation.rst 图文详解PHPStorm实现自动执行代码格式化-…...

SpringBoot中日志的使用log4j

SpringBoot中日志的使用log4j 项目中日志系统是必不可少的&#xff0c;目前比较流行的日志框架有 log4j、logback 等&#xff0c;这两个框架的作者是同一个 人&#xff0c;Logback 旨在作为流行的 log4j 项目的后续版本&#xff0c;从而恢复 log4j 离开的位置。 另外 slf4j(…...

迭代器与生成器

章节目录&#xff1a; 一、迭代器1.1 相关概述1.2 基本使用1.3 自定义迭代器 二、生成器2.1 相关概述2.2 基本使用2.3 三种应用场景 三、yield 和 class 定义的迭代器对比四、结束语 一、迭代器 1.1 相关概述 迭代是 Python 最强大的功能之一&#xff0c;是访问集合元素的一种…...

适用于 Windows 的 10 个最佳视频转换器:快速转换高清视频

您是否遇到过由于格式不兼容而无法在您的设备上播放视频或电影的情况&#xff1f;您想随意播放从您的相机、GoPro 导入的视频&#xff0c;还是以最合适的格式将它们上传到媒体网站&#xff1f;您的房间里是否有一堆 DVD 光盘&#xff0c;想将它们转换为数字格式以便于播放&…...

分布式锁的概念、应用场景、实现方式和优缺点对比

一&#xff1a;什么是分布式锁 分布式锁是一种用于协调分布式系统中多个节点对共享资源的访问的机制。在分布式系统中&#xff0c;由于多个节点的并发执行&#xff0c;可能会导致对共享资源的竞争&#xff0c;而分布式锁的目的就是确保在任何时刻&#xff0c;只有一个节点能够持…...

Linux:常见指令

个人主页 &#xff1a; 个人主页 个人专栏 &#xff1a; 《数据结构》 《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 测试&#xff08;1&#xff09;启动客户端&#xff08;2&#xff09;测试客户端操作 四、集群安装4.1…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...