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

面试热题(打家窃舍)

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

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

输入:nums = [1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

       如上图,每个房间放的金子都不同,有多有少,两个房间之间有警报相连,如果同时偷取相连的两个房子,警报就会发出,你就要去蹲局子,那么如何做一个聪明的小偷,在不触发警报的情况下偷取的金额是最大的,接下来,让我们替小偷想一个方案,如何去偷?

我们可以从后往前考虑,假如我们偷取最后一间房间

 我们是不是不可以偷取倒数第二间房间,可供的选择就是在倒数第二间之后随便选一家进行偷取

       为了利益最大化,我们是不是应该偷取的是前n-2间房子的最大金额数+最后一间房子的最大金额数就是我们当前可以偷取的最大金额数呢?NONONO,我们还有一种不偷取最后一间房子的情况,偷取n-2房间的情况

 我们通过上述的推导就可以将动态转移方程写出来

 dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]);

我们设置的dp数组的语意是dp[i]是,偷取第i家的最大金额数

       我们可以很简单的推导出基本情况,如果没有房间,小偷就得被饿死,如果只有一家,小偷无可奈何,只能被迫的去偷这家,如果有两家,小偷肯定回去偷金额比较多的那家

     dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);

解题的入参判断肯定少不了,这种入参判断能为你解决不少的麻烦

       if(n==0){return 0;}if(n==1){return nums[0];}

那么我们的代码 就已经写完了

public int rob(int[] nums) {int n=nums.length;if(n==0){return 0;}if(n==1){return nums[0];}int [] dp=new int[n];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(int i=2;i<n;i++){dp[i]=Math.max(dp[i-1],nums[i]+dp[i-2]);}return dp[n-1];}

       打家劫舍II的基本过程和I差不多,就是从一个直线型房屋排列转换为环形房屋排列,这种就应该考虑是n-1房子和0房子偷不偷的问题,其实可以分为两个数组,分别计算可以偷取的最大金额,最后取最大值就ok了,我们下面讲打家窃舍III

       我不得不说,这小偷的数据结构学的其实蛮好的,什么样的房屋排列都能让他想到数据结构这块,利用算法的知识进行解决,不当码农可惜了

 来让我们言归正传

 对于我们的选择是每个节点是否偷取决定着我们最后的结果

 如果偷的话,情况又是如何?不偷的时候情况又是怎样的?

 

       看到这幅图大家会想到什么?树的层序遍历,但是树的层序遍历在这里可是不适用的,因为这道题中的有些情况是通过不了,所以我们换种思维想一想,这种题是不是可以用递归的方式解决

 假设我们的当前节点是root,递归函数是rob

偷:当前的节点的金额数+rob(节点左树的子左树)+rob(节点左树的右树)+rob(节点右树的左树)+rob(节点右树的右树)

不偷:rob(节点的左树)+rob(节点的右树)

 int rob=root.val+(root.left==null?0:rob(root.left.left)+rob(root.left.right))+(root.right==null?0:rob(root.right.right)+rob(root.right.left));int rob_not=rob(root.left)+rob(root.right);

 这种递归大概率会超时,所以我们加一个记忆化数组,不用再进行重复计算(进行剪枝)

  Map<TreeNode,Integer> map=new HashMap<>();if(map.containsKey(root)){return map.get(root);}

       该题的大致流程就已经讲完了,希望大家可以看的开心,不懂的可以在评论区问我,我看到的话会给大家一一解答

   Map<TreeNode,Integer> map=new HashMap<>();public int rob(TreeNode root) {if(root==null){return 0;}if(map.containsKey(root)){return map.get(root);}int rob=root.val+(root.left==null?0:rob(root.left.left)+rob(root.left.right))+(root.right==null?0:rob(root.right.right)+rob(root.right.left));int rob_not=rob(root.left)+rob(root.right);int max=Math.max(rob,rob_not);map.put(root,max);return max;}

相关文章:

面试热题(打家窃舍)

一个专业的小偷&#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金&#xff0c;影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入&#xff0c;系统会自动报警。 给定一个代表每个房屋存放金额的非负…...

【Deepsort】C++版本Deepsort编译(依赖opencv,eigen3)

目录 下载源码安装onnxruntime安装Eigen3编译opencv 下载源码 https://github.com/shaoshengsong/DeepSORT安装onnxruntime 安装方法参考博客 安装Eigen3 当谈及线性代数计算库时&#xff0c;Eigen3是一个强大而受欢迎的选择。Eigen3是一个C模板库&#xff0c;提供了许多用…...

Synchronized锁升级过程

无锁状态&#xff08;无锁&#xff09;&#xff1a;当一个线程访问一个没有被锁定的Synchronized代码块时&#xff0c;处于无锁状态。此时&#xff0c;线程可以直接进入临界区执行代码&#xff0c;不需要进行任何锁协调。 偏向锁状态&#xff08;偏向锁&#xff09;&#xff1…...

汽车电子功能安全

功能安全考虑 分析方法&#xff1a;FMEA&#xff0c;DFMEA&#xff08;设计潜在失效模式和影响分析&#xff09; 严重度&#xff08;Severity&#xff09;&#xff0c;暴露率&#xff08;Exposure&#xff09;&#xff0c;可控性&#xff08;Controllability&#xff09;评估…...

ARM进阶:内存屏障(DMB/DSB/ISB)的20个使用例子详解

在上一节内存屏障指令之DMB、DSB和ISB详解中&#xff0c;介绍了一下内存屏障的三个指令的作用并举了一些例子&#xff0c;对于内存屏障指令的使用时机&#xff0c;与处理器架构(比如Cortex-M和Cortex-A)和处理器的系统实现(同样的架构&#xff0c;有不同的实现&#xff0c;如ST…...

Cpp学习——模板

模板&#xff1f; 目录 模板&#xff1f; 1.介绍 2.函数模板的使用 3.函数模板的强制转换or显式调用 四,模板的分类 1.介绍 在Cpp3.0中&#xff0c;祖师爷便引入了模板的概念。这是一个重大的变革&#xff0c;为后来的Cpp标准化打下了铺垫。也正是因为有了模板&#xff0…...

HTTP 协议 版本详解

HTTP 协议 介绍<一> 简介 HTTP&#xff08;Hypertext Transfer Protocol&#xff09;是一种用于在客户端和服务器之间进行通信的协议。它是现代互联网中最常用的应用层协议之一。HTTP 的主要目的是实现超文本资源的传输&#xff0c;例如 HTML 文档、图像和音频文件等。…...

PHP语言基础知识(超详细)

文章目录 前言第一章 PHP语言学习介绍 1.1 PHP部署安装环境1.2 PHP代码工具选择 第二章 PHP代码基本语法 2.1 PHP函数知识介绍2.2 PHP常量变量介绍 2.2.1 PHP变量知识&#xff1a;2.2.2 PHP常量知识&#xff1a; 2.3 PHP注释信息介绍2.4 PHP数据类型介绍 2.4.1 整形数据类型2.4…...

Flex弹性盒子的项目属性

最近在写项目时用到了弹性盒子的项目属性&#xff0c;记录一下&#xff0c;以后用到继续扩充 <div class"concern-data"><div><img src"https://meituan.thexxdd.cn/lvyou/assets/pinglun-fc62482a.svg" alt""><span>1&…...

广州银行信用卡中心:强化数字引擎安全,实现业务稳步增长

广州银行信用卡中心是全国城商行中仅有的两家信用卡专营机构之一&#xff0c;拥有从金融产品研发至销售及后期风险控制、客户服务完整业务链条&#xff0c;曾获“2016年度最佳创新信用卡银行”。 数字引擎驱动业务增长 安全左移降低开发风险 近年来&#xff0c;广州银行信用卡…...

【Rust日报】2023-08-03 - Polars 获约 400 万美元种子轮融资

文章&#xff1a;2023 年对 Rust 编译器 CI 的改进 kobzol 的新文章&#xff0c;介绍了关于优化 Rust 编译器构建、测试和性能监视基础设施的方案和实施情况。 根据作者的工作&#xff0c;文章内容分为三类&#xff1a; Rust 编译器&#xff08;rustc&#xff09;构建配置、 Ru…...

装修小程序,开启装修公司智能化服务的新时代

随着数字化时代的来临&#xff0c;装修小程序成为提升服务质量和效率的关键工具。装修小程序旨在为装修公司提供数字化赋能、提高客户满意度的智慧装修平台。通过装修小程序&#xff0c;装修公司能够与客户进行在线沟通、展示设计方案、提高服务满意度等操作。 装修小程序的好处…...

使用PHP和Redis实现简单秒杀功能

安装Redis 首先&#xff0c;需要在服务器上安装Redis。如果使用Linux系统&#xff0c;可以使用命令行安装。如果使用Windows系统&#xff0c;可以下载并安装Redis二进制文件。 创建Redis连接 在PHP中&#xff0c;可以使用Redis扩展来连接Redis服务器。需要在PHP文件中包含Re…...

C#开发FFMPEG例子(API方式) FFmpeg拉取udp组播流并播放

代码及工程见https://download.csdn.net/download/daqinzl/88168680 开发工具&#xff1a;visual studio 2019 网上用C/C调用FFmpeg的API例子很多&#xff0c; c#使用ffmpeg.autogen的方式很简单&#xff0c;直接复制C/C调用FFmpeg的API的代码到C#中&#xff0c;然后在FFmpeg…...

Android性能优化—图片优化

图片优化是内存优化中很重要的一部分&#xff0c;加载Bitmap时往往需要消耗大量的内存&#xff0c;稍不注意就容易导致内存溢出&#xff08;OOM&#xff09;。 一、图片OOM问题产生 1、 一个页面一次加载过多图片&#xff1b; 2、加载大图片没有进行压缩(尺寸&#xff0c;质…...

如何搭建自动化测试框架?资深测试整理的PO模式,一套打通自动化...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 Po模型介绍 1、简…...

软件外包开发的GO语言特点

Go语言&#xff08;也称为Golang&#xff09;是由Google开发的一种编程语言。它具有许多特点&#xff0c;使其成为许多项目范围的优秀选择。Go语言适用于需要高性能、并发和简洁易读的项目&#xff0c;特别是面向网络和分布式应用的项目。今天和大家分享项目的特点及适用的项目…...

【深度学习Week4】MobileNet_ShuffleNet

报错&#xff1a;unsafe legacy renegotiation disabled 解决方案&#xff1a; 尝试了更换cryptography36.0.2版本&#xff0c;以及更换下载链接的方法&#xff0c;都不行&#xff0c;最后采用了手动下载mat文件并上传到colab的方法 高光谱图像分类数据集简介Indian Pines&…...

649. Dota2 参议院

题目描述&#xff1a; 主要思路&#xff1a; 这是一个按照题意模拟的问题&#xff0c;利用队列模拟议员的投票顺序即可。 class Solution { public:string predictPartyVictory(string senate) {queue<int> r,d;int nsenate.length();for(int i0;i<n;i){if(senate[i…...

无人机管控平台,推动电力巡检管理水平提升

各地区无人机作业水平和管理水平存在参差不齐&#xff0c;电力巡检管理要求与业务发展水平不匹配的问题。同时&#xff0c;巡检数据的存储和管理分散&#xff0c;缺乏有效的整合与共享手段&#xff0c;使得内外业脱节&#xff0c;没有形成统一应用和闭环管理。这就导致巡检数据…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...