LeetCode算法题(Go语言实现)_61
题目
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
一、代码实现(动态规划优化)
func rob(nums []int) int {prev, curr := 0, 0for _, num := range nums {prev, curr = curr, max(curr, prev + num)}return curr
}func max(a, b int) int {if a > b {return a}return b
}
二、算法分析
1. 核心思路
- 滚动变量优化:仅维护前两个状态(前前最大值和前一最大值)
- 状态转移方程:当前最大值 = max(前一最大值, 前前最大值 + 当前房屋金额)
- 贪心选择:每一步选择局部最优解推进全局最优解
2. 关键步骤
- 初始化状态:prev=0(前前状态),curr=0(前一状态)
- 遍历房屋:
- 计算当前房屋两种决策的最大值
- 滚动更新前两个状态值
- 结果返回:最终curr即为全局最优解
3. 复杂度
指标 | 值 | 说明 |
---|---|---|
时间复杂度 | O(n) | 线性遍历所有房屋 |
空间复杂度 | O(1) | 仅使用两个临时变量 |
三、图解示例
四、边界条件与扩展
1. 特殊场景验证
- 空数组:返回0
- 单房屋:直接返回该房屋金额
- 双房屋:返回金额较大值
- 全零数组:正确返回0
- 交替大数:正确选择非相邻房屋
2. 扩展应用
- 网络安全:选择不冲突节点进行渗透测试
- 资源分配:优化不重叠任务的收益
- 路径规划:寻找收益最大的不连续路径
3. 多语言实现
class Solution {public int rob(int[] nums) {int prev = 0, curr = 0;for (int num : nums) {int temp = Math.max(curr, prev + num);prev = curr;curr = temp;}return curr;}
}
class Solution:def rob(self, nums: List[int]) -> int:prev, curr = 0, 0for num in nums:prev, curr = curr, max(curr, prev + num)return curr
五、总结与优化
1. 算法对比
方法 | 优势 | 适用场景 |
---|---|---|
动态规划 | 时间复杂度最优 | 常规场景 |
递归+记忆化 | 代码直观 | 教学演示 |
矩阵快速幂 | O(log n)时间复杂度 | 极大n值计算 |
2. 工程优化
- 循环展开:手动展开循环减少分支判断
- SIMD指令:利用并行计算加速向量运算
- 预计算缓存:存储常用结果减少重复计算
3. 扩展方向
- 环形房屋:处理首尾相连的特殊情况
- 多维约束:考虑时间、空间等多维度限制
- 概率模型:引入成功概率的随机决策模型
相关文章:
LeetCode算法题(Go语言实现)_61
题目 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金…...
Kafka消息不丢失处理
kafka作为消息中间件,吞吐量大(至于为啥吞吐量大,本文不做介绍),所以大家用的多。涉及到异构数据库更换,以及数据预处理后的迁移,基本想到的都是通过kafka。 概览图 我先画个图 生产者到kafka…...
Python+ffmpeg 实现给视频添加字幕
创作灵感 孩子学校经常留作业,需要提交一段录制的视频,视频上要求添加学校、班级、姓名等信息的字幕,手机自带的相机软件字幕添加位置要么只能添加在视频正中,要么无法添加多行文本,要么只能添加在片头或者片尾&#…...
QMK键盘固件自定义指南 - 打造你的专属键盘体验
QMK键盘固件自定义指南 - 打造你的专属键盘体验 🚀 前言 在机械键盘的世界里,QMK固件让你的键盘不再只是简单的输入设备,而是可以按照你的意愿定制的强大工具。本文将深入浅出地介绍如何自定义QMK键盘的行为,从基础概念到高级应…...
Linux-openeuler更换yum镜像源
将 openEuler 系统镜像源更换为华为镜像 以openEuler 24.03 LTS SP1 为例。操作前建议备份原配置文件,并确保系统已联网。 一、确认系统版本与架构 查看系统版本: [rooteulerzy yum.repos.d]# cat /etc/os-releaseNAME"openEuler"VERSION&qu…...
手势、鼠标滑动实现界面切换
手势: #include <QApplication> #include "mainwindow.h"int main(int argc, char *argv[]) {QApplication app(argc, argv);MainWindow window;window.show();return app.exec(); }#ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainW…...
什么是变量提升?(形象的比喻)
当然!可以用几个生活中的比喻来形象地解释变量提升: 1. 书架的占位符 想象你有一个书架,但还没放书。 • 变量提升(var): 你先在书架上贴了一个标签(比如写“我的书”)&…...
趣味编程:答案之书
概述:该篇博客主要介绍的是曾经一度风靡全网的答案之书小程序。 目录 1. 效果展示 2. 源码展示 3. 代码逻辑详解 3.1 头文件与全局变量 3.2 main函数 3.3 主循环 3. 4 绘制界面 4. 运行问题 5.小结 1. 效果展示 该小程序是动态的效果, 因此实…...
用kompose将docker-compose文件转换为K8S资源清单
一、什么是kompose Kompose 是什么?它是一个转换工具,可将 Compose (即 Docker Compose)所组装的所有内容转换成容器编排器(Kubernetes 或 OpenShift)可识别的形式。 更多信息请参考 Kompose 官网 Kompos…...
Linux中的防火墙
概述 防火墙通过一系列规则来过滤网络数据包,决定哪些数据包可以进入或离开系统,哪些数据包将被阻止,以此来保护系统免受未经授权的访问、恶意攻击和潜在的安全威胁。 常见的防火墙软件 iptables:是 Linux 系统中常用的防火墙工…...
AI开发跃迁指南(第三章:第四维度1——Milvus、weaviate、redis等向量数据库介绍及对比选型)
1.向量数据库简介 向量数据库(Vector Database)是专门为存储和查询高维向量数据而设计的数据库,主要用于处理由机器学习模型生成的嵌入向量(Embeddings)。它在人工智能(AI)、自然语言处理&…...
深度学习笔记41_调用Gensim库训练Word2Vec模型
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 | 接辅导、项目定制 一、我的环境 1.语言环境:Python 3.8 2.编译器:Pycharm 3.深度学习环境: torch1.12.1cu113torchvision…...
Windows Server 2025 安装AMD显卡驱动
运行显卡驱动安装程序,会提示出问题。但是此时资源已经解压 来到驱动路径 C:\AMD\AMD-Software-Installer\Packages\Drivers\Display\WT6A_INF 打开配置文件,把这两行替换掉 %ATI% ATI.Mfg, NTamd64.10.0...16299, NTamd64.10.0, NTamd64.6.0, NTamd64.…...
debian安装docker
debian安装docker <在Debian上安装Docker的步骤》 在Debian上安装Docker通常涉及几个步骤,以确保你能够顺利运行Docker容器。下面是一份详细的指南,帮助你在Debian系统上安装Docker。 1. 更新你的包列表 首先,更新你的包列表以确保所有…...
uniapp上架苹果APP Store踩雷和部分流程注意事项(非完整流程)
本文是uniapp打包成ios上架到苹果商店一系列踩雷和部分流程介绍 1.打包需要俩个证书 需要xx..mobileprovision和xx.p12证书并且ios打包一天最多5次,超出需要2元/1次付费打包,证书需要使用苹果电脑生成,以下为证书生成教程iOS证书(.p12)和描述…...
【吃透 Elasticsearch 的核心原理】学习步骤
要真正,需深入以下关键机制(结合最新技术演进): 一、倒排索引机制 核心三要素 Term Index:FST 结构加速前缀匹配(如 ap* 查询)Term Dictionary:存储所有 token 及统计信息ÿ…...
springboot使用mybatisPlus进行数据库增删改查
springboot使用mybatisPlus进行数据库增删改查 提示:帮帮志会陆续更新非常多的IT技术知识,希望分享的内容对您有用。本章分享的是springboot的使用。前后每一小节的内容是存在的有:学习and理解的关联性。【帮帮志系列文章】:每个…...
移动端前端开发中常用的css
在开发移动端项目的时候,很多样式都是相同的,比如说图标大小,头像大小,页面底部保存(添加按钮),项目主体颜色等等,对于这些在项目中常用到的,通常都会写在公共样式中(pub…...
C/C++内存分布
内存分布示意图: 内存分布各区域详解: 内核空间: 放置操作系统相关的代码和数据。(用户不能直接进行操作 ------ 可以通过调用系统提供的 api 函数) 栈区: 又叫堆栈,非静态局部变量/函数参数/…...
Sass @import rules are deprecated and will be removed in Dart Sass 3.0.0.
版本: 原因 在 Dart Sass 3.0.0 中, @import 规则将被弃用,推荐使用 @use 和 @forward 规则来替代。 1.@use替代@import @use 规则允许你引入其他 Sass 文件中的变量、混合器和函数,并且可以避免命名冲突。 示例: style.scss @use variables;body {color: variables.$pr…...
【计算机网络】用户从输入网址到网页显示,期间发生了什么?
1.URL解析 浏览器分解URL:https://www.example.com/page 协议:https域名:www.example.com路径:/page 2.DNS查询: 浏览器向DNS服务器发送查询请求,将域名解析为对应的IP地址。 3.CDN检查(如果有)&#…...
使用adb设置wifi相关
其他的可以参考以下指令 Android 使用adb操作WiFi连接扫描等相关指令_adb wifi-CSDN博客 但是如果你的wifi账号出现中文的时候: 例如:ssid "wolf的网络" 这种类型的时候,直接使用adb指令是有问题的,基本都会出现乱码…...
MySQL数据库创建、删除、修改
一:建库建表 我们以学校体系进行建表。将数据库命名为school。 以下代码中的大写均可小写不影响。如CREATE DATABASE与create database相同 四个关键的实体分别是学院、老师、学生和课程,其中,学生跟学院是从属关系,这个关系从…...
【Android】动画原理解析
一,基础动画 基础动画,有四种,分别是平移(Translate)、缩放(Scale)、Rorate(旋转)、Alpha(透明度),对应Android中以下四种。 1,Animation基类 1,基本概念 1,插值器 插值器的作用,是控制动画过程的参数,可以理解为 时间(t)与动画进程(d)的函数,动画仅…...
C++从入门到实战(十四)初识STL与STL简介
C从入门到实战(十四)初识STL与STL简介 前言一、什么是 STL?二、STL 的版本三、STL六大组件(目前了解即可,后面会逐步讲解)1. 容器(Containers)—— 装数据的“盒子”2. 算法…...
力扣-142.环形链表II
题目描述 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 不允许修改 链表。 class Solution { public:ListNode *detectCycle(ListNode *head) {ListNode *fast head;ListNode *slow head;while (fast) {…...
ERC-20与ERC-721:区块链代币标准的双星解析
一、代币标准的诞生背景 在以太坊生态中,代币标准是构建去中心化应用(DApps)的基石。ERC-20与ERC-721分别代表同质化与非同质化代币的两大核心标准,前者支撑着90%以上的加密资产流通,后者则开启了数字资产唯一性的新时…...
图像管理与人脸识别工具深度解析
这篇Python应用程序代码实现了一个功能丰富的图像管理和人脸识别工具,它集成了多种实用功能,包括人脸检测与裁剪、屏幕截图以及生成PDF等核心功能。我将深入分析这个应用程序的架构、功能和实现方式,帮助读者理解其设计思路和关键技术点。 C…...
【图片合并PDF】一次性将多个文件夹里的图片批量按文件夹为单位合并PDF,多个文件夹图片合并PDF,基于WPF的实现方案
设计行业:设计师需要将项目设计稿按文件夹整理并合并为PDF交付客户 摄影行业:摄影师按主题分类的照片需要合并为PDF存档或分享 企业文档管理:市场调研部门需要将分散在不同文件夹的调研图片合并为PDF报告 教育领域:教师需要将学生的作业图片按班…...
Matlab 数控车床进给系统的建模与仿真
1、内容简介 Matlab217-数控车床进给系统的建模与仿真 可以交流、咨询、答疑 2、内容说明 略 摘 要:为提高数控车床的加工精度,对数控 车床进给系统中影响加工精度的主要因素进行了仿真分析研 动系统的数学模型,利用MATLAB软件中的动态仿真工具 究:依据机械动力学原理建立了…...
HOW - 在 Mac 上的 Chrome 浏览器中调试 Windows 场景下的前端页面
文章目录 为什么需要模拟 Windows 环境?一、修改 User-Agent 模拟 Windows 浏览器方法 1:通过 Chrome 开发者工具修改 UA方法 2:使用浏览器插件 二、模拟 Windows 的字体和滚动条样式1. 模拟 Windows 字体2. 强制显示滚动条(模拟 …...
微信小程序执行C语言库的详细方案
以下是微信小程序中执行C语言库的详细技术方案,分为环境准备、开发流程、优化技巧三个部分: 一、环境准备阶段 1. 工具链安装 # 安装Emscripten核心工具链 git clone https://github.com/emscripten-core/emsdk.git cd emsdk ./emsdk install latest .…...
如何用分布式防御抵扣大规模DDoS攻击?
DDoS攻击是当前最严峻的网络安全威胁之一,其通过海量请求耗尽目标资源,导致服务瘫痪。面对攻击规模的指数级增长,传统的单点防御已难以应对。本文将结合最新技术趋势,探讨分布式防御体系在抵御大规模DDoS攻击中的核心策略与实践。…...
【MySQL】存储引擎 - MyISAM详解
📢博客主页:https://blog.csdn.net/2301_779549673 📢博客仓库:https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! &…...
如何在Jmeter中调用C程序?
在JMeter中调用C语言程序可以通过以下几种方式实现: 方法一:使用OS Process Sampler JMeter的“OS Process Sampler”可以用来调用外部程序,包括C语言编写的可执行文件。 步骤: 准备C语言程序: 编写C语言代码并编译…...
PyTorch 版本、torchvision 版本和 Python 版本的对应关系
PyTorch 版本、torchvision 版本和 Python 版本的对应关系 在深度学习领域,PyTorch 及其配套库 torchvision 的使用极为广泛。但不同版本的 PyTorch、torchvision 与 Python 之间存在严格的对应关系,若版本搭配不当,会导致代码运行出错…...
构建高可维护、易测试的异步任务系统:基于 Celery + Redis + Eventlet 的模块化架构实践
引言:为什么我们需要一个结构清晰的异步任务系统? 在现代软件开发中,异步任务已经成为提升响应性能、解耦业务逻辑、支持高并发的重要手段。尤其对于测试工程师而言,异步任务往往意味着: 任务执行不可控状态追踪困难…...
《智能网联汽车 自动驾驶功能场地试验方法及要求》 GB/T 41798-2022——解读
目录 1. 适用范围与核心目标 2. 试验核心要求 2.1 试验场地与环境 2.2 试验设备与数据采集 2.3 试验车辆要求 3. 试验过程与通过条件 4. 关键试验场景与方法 4.1 交通信号识别及响应 4.2 基础设施与障碍物识别 4.3 行人及非机动车场景 4.4 紧急避险与风险策略 5. 特…...
删除链表倒数第N个节点
Leetcode(19): 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 分析: 首要目标就是找到第N个节点的前一个节点,因为只有通过这个节点(cur)才可进行对…...
创建型模式:抽象工厂(Abstract Factory)模式
一、概念与核心思想 抽象工厂(Abstract Factory)模式是创建型设计模式的重要成员,它提供一个创建一系列相关或相互依赖对象的接口,而无需指定它们具体的类。该模式将对象的创建逻辑封装在抽象工厂及其具体实现类中,客户端通过抽象工厂接口获取所需的对象族,实现对象创…...
预训练模型实战手册:用BERT/GPT-2微调实现10倍效率提升,Hugging Face生态下的迁移学习全链路实践
更多AI大模型应用开发学习内容,尽在聚客AI学院。 一. 预训练模型(PTM)核心概念 1.1 什么是预训练模型? 预训练模型(Pre-trained Model, PTM)是在大规模通用数据上预先训练的模型,通过自监督学…...
基于Flink的用户画像 OLAP 实时数仓统计分析
1.基于Flink的用户画像 OLAP 实时数仓统计分析 数据源是来自业务系统的T日数据,利用kakfa进行同步 拼接多个事实表形成大宽表,优化多流Join方式,抽取主键和外键形成主外键前置层,抽取外键和其余内容形成融合层,将4次事…...
php java go python面向对象的设计原则和常用设计模式
一、面向对象设计原则(OOP Design Principles) 是写出高内聚、低耦合、可维护系统的基础,重点是 SOLID 五大原则 其他补充原则。 📌 SOLID 五大设计原则: 原则名称全称核心思想示例关键词S 单一职责原则Single Respo…...
第十三节:图像形态学操作-腐蚀与膨胀
引言 图像形态学是数字图像处理领域中的一个重要分支,它主要研究图像中物体的形状和结构。作为形态学操作的基础,腐蚀(Erosion)和膨胀(Dilation)是两种最核心的操作,广泛应用于图像预处理、特征提取、目标检测等多个领域。OpenCV作为最流行的…...
数据结构 - 9( 位图 布隆过滤器 并查集 LRUCache 6000 字详解 )
一:位图 位图是一种高效的数据结构,它通过比特来表示某个值的存在与否,通常以连续的二进制位数组存储。每个比特位对应一个特定的状态,这种表示方式在内存效率和操作速度上具有显著优势,尤其适用于海量数据、整数以及…...
在Hugging Face网站像Github一样克隆repository到本地的具体步骤
首先我们找到自己想要的仓库,在搜索栏进行搜索 之后我们可以看到这里有三个点,鼠标点击,选择Clone repository 最后按照上面的步骤进行复制粘贴到电脑上执行就行,我们可以看到有两种选择HTTPS和SSH,如果HTTPS不行就选择…...
如何使用Java从PDF文件中提取图像(教程)
Java本身不直接支持PDF文件操作,因此需要使用外部Java PDF库。本教程将向您展示如何通过5个简单步骤,使用JPedal Java PDF库从PDF文件中提取图像。 使用Java从PDF中提取图像 • 将JPedal库添加到您的类路径或模块路径(下载试用版jar文件&…...
通过混合机器学习和 TOPSIS 实现智能手机身份验证的稳健行为生物识别框架
1. 简介 随着日常工作、个人生活和金融操作对智能手机的依赖性不断增强,对弹性安全身份验证系统的需求也日益增长。尽管 PIN 码、密码和静态生物识别等传统身份验证方法仍可为系统提供一定的安全级别,但事实证明,它们容易受到多种威胁,包括敏感数据泄露、网络钓鱼、盗窃和…...
day010
文章目录 1. 在Ubuntu中使用visudo2. 别名 alias2.1 查看已配置的别名2.2 配置grep别名2.3 配置rm别名2.4 临时使用配置别名的命令 3. 系统校验检查3.1 md5校验3.2 aide 高级入侵检测环境3.2.1 安装aide3.2.2 修改aide配置文件3.2.3 根据配置文件生成初始的指纹信息库3.2.4 使用…...
Coco AI 开源应用程序 - 搜索、连接、协作、您的个人 AI 搜索和助手,都在一个空间中。
一、软件介绍 文末提供程序和源码下载 Coco AI 是一个统一的搜索平台,可将您的所有企业应用程序和数据(Google Workspace、Dropbox、Confluent Wiki、GitHub 等)连接到一个功能强大的搜索界面中。此存储库包含为桌面和移动设备构建的 Coco 应…...