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

从零学算法

198.你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 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 。

  • 我的原始人解法:首先试一下分成一个个子问题,很容易想到的是,偷到 1 号房屋为止的最高金额,偷到 2 号房屋为止的最高金额…, 那么就有 f[i] 为偷到最后一个房屋为 i 时的最高金额(不一定就偷了 i 房屋,只是范围到 i 为止),接着找关联性,注意限制条件不能偷连续的房屋,首先 f[0] ,只能偷房屋 1,就直接为 nums[0] ,接着 f[1] 开始有说法了,两个房屋,我要么偷了前一个,这个不偷了,要么前一个没偷,我偷这个,两者我取最大值,所以为 max(f[0],nums[1]), f[2] ,同理 f[2] 也是两种可能,如果我偷了前一个房屋,那么我这个房屋是肯定不能偷了,也就是说我只能是 f[2-1],而如果我前一天没偷,那么我今天必偷无疑,也就是 f[2-2] + nums[2],两者之中我取最大的可能性即可,以此类推,这也就得到了状态转移方程和初始值。为了方便我定义数组时长度加了 1,表示第一天的时候,前一天(逻辑上不存在,所以正好为 0)不偷的金额为 0,偷则为 nums[0]。
  •   public int rob(int[] nums) {int m = nums.length;int[] f = new int[m+1];f[1] = nums[0];for(int i=2; i<=m; i++){f[i] = Math.max(f[i-1],f[i-2]+nums[i-1]);}return f[m];}
    
  • 由于我们只需要知道前一天偷或不偷,所以定义两个变量滚动更新记录就足够了,不需要数组
  •   int m = nums.length;int x1=0,x2=nums[0];for(int i=2; i<=m; i++){int temp = Math.max(x2,x1+nums[i-1]);x1 = x2;x2 = temp;}return Math.max(x1,x2);
    
  • 他人题解我就不看了

相关文章:

从零学算法

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

《Linux0.11源码解读》理解(四) head之重新设置IDT/GDT

上节提到&#xff0c;现在cs:ip指向0地址&#xff0c;此处存储着作为操作系统核心代码的system模块&#xff0c;是由head.s和 main.c以及后面所有源代码文件编译链接而成。head.s(以下简称head)紧挨着main.c&#xff0c;我们先执行head。 重新设置内核栈 _pg_dir: _startup_3…...

<SQL>《SQL命令(含例句)精心整理版(4)》

《SQL命令&#xff08;含例句&#xff09;精心整理版&#xff08;4&#xff09;》 14 数据库对象14.1 表14.2 视图14.3 存储过程14.3.1 概念14.3.2 创建存储过程14.3.2 调用存储过程14.3.3 DbVisualizer工具中调用方法14.3.3 DB2命令行脚本调用方法14.3.4 DB2中两个存储过程报错…...

C++死锁

死锁是指两个或两个以上的线程在执行过程中&#xff0c;由于竞争资源或者由于彼此通信而造成的一种阻塞的现象&#xff0c;若无外力作用&#xff0c;它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁&#xff0c;这些永远在互相等待的状态称为死锁。 死锁通常发生…...

[自学记录02|百人计划]纹理压缩

一、什么是纹理压缩 纹理压缩是为了解决内存、带宽问题&#xff0c;专为在计算机图形渲染系统中存储纹理而使用的图像压缩技术。 1.图片格式和纹理格式的区别 (1)图片格式 图片格式是图片文件的存储格式&#xff0c;通常在磁盘、内存中储存和传输文件时使用&#xff1b;例如…...

C++泛型编程之模板

目录 一、什么是泛型编程 二、函数模板 2.1函数模板的概念 2.2函数模板格式 2.3函数模板的原理 2.5函数模板的实例化 2.6模板参数的匹配原则 三、类模板 3.1类模板的定义格式 3.2 类模板的实例化 四、非类型模板参数 五、模板的特化 5.1模板特化的概念&#xff1a;…...

极氪汽车 APP 系统云原生架构转型实践

作者&#xff1a;极氪汽车 前言 新能源汽车已经成为我国汽车市场再次崛起的关键支柱&#xff0c;随着新能源汽车市场的快速发展&#xff0c;不同类型的品牌造车厂商呈现出百花齐放的态势。极氪汽车是吉利控股集团旗下高端纯电汽车新品牌&#xff0c;2021 年 4 月极氪发布首款…...

一个UDP下载服务器的实现(模拟下载文件)

本期分享的主要是使用UDP实现文件下载功能&#xff0c;需要自己编写服务器和客户端&#xff0c;实现的功能主要有以下几个&#xff1a; &#xff08;1&#xff09;服务器可以为请求的用户下发文件数据&#xff08;前提是服务器得有这个数据文件&#xff09; &#xff08;2&…...

01.hadoop上课笔记之hadoop介绍

1.大数据介绍 可以对未来数据预测 google通过搜索预测流感,足球球员有一 定关联…caict可以得到数据hbase hive林子雨mooc数据要进行挖掘(推断更多信息) 2.大数据是非结构化数据多:声音,图片… 3.大数据影响因素 大多快低 tb pb eb zb 1.硬件 2.网络带宽 4.大数据的特征 数据量…...

小鹏汽车Q1财报:押注G6、大力降本,明年智驾BOM降半

‍作者 | 德新编辑 | 王博 小鹏汽车本周发了Q1财报&#xff0c;数据不好看&#xff0c;以致于在微博端也发了公开信。 那后续呢&#xff1f; 小鹏第二季度指引是&#xff0c;总交付数量约为2.1 - 2.2万辆&#xff0c;收入预计约为45 - 47亿元&#xff1b;四季度&#xff0c…...

VMware ESXi 8.0U1a 发布 - 领先的裸机 Hypervisor

VMware ESXi 8.0U1a 发布 - 领先的裸机 Hypervisor 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-esxi-8-u1/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.org 2023-06-01, VMware vSphere 8.0U1a 发布。 详见&am…...

Unity的IPreprocessBuild:深入解析与实用案例

Unity IPreprocessBuild Unity IPreprocessBuild是Unity引擎中的一个非常有用的功能&#xff0c;它可以让开发者在构建项目时自动执行一些操作。这个功能可以帮助开发者提高工作效率&#xff0c;减少手动操作的时间和错误率。在本文中我们将介绍Unity IPreprocessBuild的使用方…...

htmlCSS-----CSS选择器(下)

目录 前言&#xff1a; 2.高级选择器 &#xff08;1&#xff09;子代选择器 &#xff08;2&#xff09;伪类选择器 &#xff08;3&#xff09;后代选择器 &#xff08;4&#xff09;兄弟选择器 相邻兄弟选择器 通用兄弟选择器 &#xff08;5&#xff09;并集选择器 &am…...

RDK X3 Module发布,全新软硬件平台加速实现量产级产品落地

机器人开发是一段美妙的旅程。GEEKROS创始人杨状状是地平线社区的一名开发者&#xff0c;热衷于鼓捣各类机器人&#xff0c;2022年&#xff0c;状状第一时间就拿到了地平线旭日X3派&#xff08;简称旭日X3派&#xff09;&#xff0c;基于TogetheROS™.Bot机器人操作系统&#x…...

【面试实战】Redis缓存设计

文章目录 Redis缓存出现的问题🙎‍♂️面试官:什么是缓存雪崩?🙎‍♂️面试官:怎样解决缓存雪崩?🙎‍♂️面试官:什么是缓存击穿?🙎‍♂️面试官:怎样解决缓存击穿?🙎‍♂️面试官:什么是缓存穿透?🙎‍♂️面试官:怎样解决缓存穿透?🙎‍♂️面试官:…...

如何解决js定时器不准确问题

为什么会出现定时器不准确呢&#xff1f; 这个其实就得提到js执行机制了&#xff0c;叫做事件循环Eventloop 循环机制中&#xff0c;异步事件 setInterval 到时后会把回调函数放入消息队列中Event Queue&#xff0c;主线程的宏任务执行完毕后依次执行消息队列的微任务&#xff…...

学习笔记——vue中使用el-dropdown组件报错

今天在工作中&#xff0c;发现使用el-select做的下拉框&#xff0c;下拉菜单展开后&#xff0c;鼠标点击下拉框之外的区域时&#xff0c;下拉菜单没有收起。然后&#xff0c;我打开控制台&#xff0c;发现了这个错误。 Uncaught TypeError: Cannot read properties of null (re…...

Java之旅(八)

Java 条件运算符 Java 条件运算符用于根据一个条件表达式的布尔值来决定程序执行的流程。条件运算符有三种类型&#xff1a;if、else 和 switch。 if 语句的一般格式如下&#xff1a; if (condition) {// 条件为 true 执行的代码块 } 其中&#xff0c;condition 是一个 bool…...

华为OD机试真题(Java),四则运算(100%通过+复盘思路)

一、题目描述 输入一个表达式(用字符串表示),求这个表达式的值。 保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’, ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。 数据范围:表达式计算结果和过程中满足∣val∣≤1000 ,字符串长度满…...

HTML表单标签form分析

说明&#xff1a;在html的标签中&#xff0c;表单标签与后台联系密切&#xff0c;像用户登录、注册&#xff0c;都是用到页面的表单标签&#xff0c;用户将信息填入到表单中&#xff0c;提交到后端业务中校验处理&#xff0c;再将结果反馈给前端页面。 表单内的标签分别有&…...

【AI】可以操控鼠标的智能体

2026-04-02&#xff0c;以下是当前&#xff08;截至2026年初&#xff09;可以操作鼠标的AI智能体最新格局&#xff0c;分为操作系统级控制&#xff08;真鼠标键盘控制&#xff09;和浏览器级控制两类&#xff1a;第一梯队&#xff1a;操作系统级鼠标控制&#xff08;全桌面操控…...

SEO 实战培训班在哪里_SEO 优化师培训在哪里

SEO 实战培训班在哪里_SEO 优化师培训在哪里 在当今数字化时代&#xff0c;网站的流量和排名直接关系到企业的生存和发展。这就是为什么越来来越多的企业和个人希望掌握SEO优化技能&#xff0c;成为一名优秀的SEO优化师。SEO 实战培训班在哪里呢&#xff1f;SEO 优化师培训在哪…...

用九齐单片机NY8B062F定时器实现精准延时与系统时基:从4ms中断到1秒计时的完整工程实践

九齐单片机NY8B062F定时器工程实战&#xff1a;构建高精度时基与延时系统 在嵌入式系统开发中&#xff0c;定时器如同设备的心跳&#xff0c;为各类功能提供精准的时间基准。九齐NY8B062F作为一款高性价比8位单片机&#xff0c;其四组灵活配置的定时器资源尤其适合小家电、智能…...

CDA Level-2 考试全攻略:从报名到备考的保姆级教程(含最新题库资源)

CDA Level-2 考试全攻略&#xff1a;从报名到备考的保姆级教程 最近两年数据分析师认证热度持续攀升&#xff0c;CDA认证作为国内认可度较高的专业证书之一&#xff0c;Level-2考试通过率常年维持在40%左右。不同于Level-1的基础考核&#xff0c;Level-2更注重实际分析能力与统…...

3步解锁加密音乐:ncmdumpGUI技术解析与实战指南

3步解锁加密音乐&#xff1a;ncmdumpGUI技术解析与实战指南 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换&#xff0c;Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI ncmdumpGUI是一款专为网易云音乐用户设计的NCM文件…...

如何在5分钟内快速上手Wade搜索库:终极快速入门指南

如何在5分钟内快速上手Wade搜索库&#xff1a;终极快速入门指南 【免费下载链接】wade :ocean: Blazing fast 1kb search library 项目地址: https://gitcode.com/gh_mirrors/wa/wade Wade是一个轻量级、高性能的JavaScript搜索库&#xff0c;仅1kb大小却提供了强大的全…...

终极AI图像分层指南:3分钟将复杂插画变成可编辑PSD图层

终极AI图像分层指南&#xff1a;3分钟将复杂插画变成可编辑PSD图层 【免费下载链接】layerdivider A tool to divide a single illustration into a layered structure. 项目地址: https://gitcode.com/gh_mirrors/la/layerdivider 你是否曾面对一幅精美的数字插画&…...

实战应用:基于openclaw在快马平台开发招聘信息采集系统

最近在做一个招聘信息分析的小项目&#xff0c;需要从各大招聘网站采集数据。经过一番调研&#xff0c;发现openclaw这个工具在数据采集方面表现相当不错&#xff0c;特别是在处理复杂页面和反爬机制上很有优势。下面分享一下我在InsCode(快马)平台上开发这个系统的实战经验。 …...

腾讯云端Openclaw+飞书 多机器人配置全攻略(新手友好版)

前言&#xff1a;随着AI自动化工具的普及&#xff0c;Openclaw凭借强大的自主执行能力&#xff0c;成为很多人提升效率的首选&#xff1b;而飞书作为高效协同工具&#xff0c;其机器人功能可无缝融入日常工作流。当两者结合&#xff0c;配置多机器人实现分工协作&#xff08;如…...

10. Doris 系列第10篇:数据查询全攻略|Join/子查询/窗口函数,从基础到高级实战

适合人群&#xff1a;大数据开发、Doris查询调优工程师、数仓分析师、BI工程师核心价值&#xff1a;吃透Doris 2.x数据查询核心能力&#xff0c;掌握Join算法选型、子查询优化、多维聚合、窗口函数实战&#xff0c;解决查询慢、资源浪费、语法报错等问题系列说明&#xff1a;本…...