leetcode 2560. 打家劫舍 IV
2560. 打家劫舍 IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统,所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组
nums表示每间房屋存放的现金金额。形式上,从左起第i间房屋中放有nums[i]美元。另给你一个整数
k,表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少k间房屋。返回小偷的 最小 窃取能力。
示例 1:
输入:nums = [2,3,5,9], k = 2 输出:5 解释: 小偷窃取至少 2 间房屋,共有 3 种方式: - 窃取下标 0 和 2 处的房屋,窃取能力为 max(nums[0], nums[2]) = 5 。 - 窃取下标 0 和 3 处的房屋,窃取能力为 max(nums[0], nums[3]) = 9 。 - 窃取下标 1 和 3 处的房屋,窃取能力为 max(nums[1], nums[3]) = 9 。 因此,返回 min(5, 9, 9) = 5 。示例 2:
输入:nums = [2,7,9,3,1], k = 2 输出:2 解释:共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。
思路:
这个解法使用了二分查找的思想来确定最小窃取能力的范围。
首先,通过
min_element和max_element函数找到数组nums中的最小值和最大值,分别存储在min和max中。然后,在
while循环中进行二分查找。每次选取最小值和最大值的中间值num作为当前的窃取能力。接下来,遍历数组
nums,判断是否可以窃取其中的房屋。使用num1标记上一个房屋是否被窃取,const1记录窃取的数量。如果当前房屋的现金金额小于
num,并且上一个房屋没有被窃取,则将const1增加1,并将num1设置为true表示该房屋被窃取。如果当前房屋的现金金额大于等于
num,则将num1设置为false表示该房屋未被窃取。完成数组遍历后,比较
const1与目标窃取的房屋数量k。如果const1小于k,则说明窃取能力太低,需要增加窃取能力,更新min=num+1;否则,说明窃取能力过高,需要减小窃取能力,更新max=num-1。当
min大于max时,循环结束,结果即为最大窃取能力max。
代码
class Solution {
public:int minCapability(vector<int>& nums, int k) {// 找到数组中的最小值和最大值int min = *min_element(nums.begin(), nums.end());int max = *max_element(nums.begin(), nums.end());// 二分查找while (min <= max) {int num = (min + max) / 2; // 当前窃取能力bool num1 = false; // 上一个房屋是否被窃取int const1 = 0; // 窃取的数量for (int i = 0; i < nums.size(); i++) {if (nums[i] < num && !num1) {const1++;num1 = true;} else {num1 = false;}}if (const1 < k) {min = num + 1; // 窃取能力过低,增加窃取能力} else {max = num - 1; // 窃取能力过高,减小窃取能力}}return max; // 返回最大窃取能力}
};
相关文章:
leetcode 2560. 打家劫舍 IV
2560. 打家劫舍 IV 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统,所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。…...
正点原子lwIP学习笔记——Socket接口TCP实验
1. Socket接口TCP Client配置连接 配置步骤如下所示: sin_family设置为AF_INET表示IPv4网络协议;sin_port为设置端口号;sin_addr. s_addr设置远程IP地址;调用函数Socket创建Socket连接, 注意该函数的第二个参数SOCK_…...
【Flink】
事件驱动型应用 核心目标:数据流上的有状态计算 Apache Flink是一个框架和分布式处理引擎,用于对无界或有界数据流进行有状态计算。 运行逻辑 状态 把流处理需要的额外数据保存成一个“状态”,然后针对这条数据进行处理,并且更新状态。这就是所谓的“…...
大数据Flink(九十一):Array Expansion(数组列转行)和Table Function(自定义列转行)
文章目录 Array Expansion(数组列转行)和Table Function(自定义列转行)...
华为云云耀云服务器L实例评测|华为云云耀云服务器L实例CentOS的存储和备份策略
1 华为云云耀云服务器L实例介绍 华为云云耀云服务器L实例是华为云计算服务中的一种虚拟云服务器,它提供了强大的计算资源,可以在云端运行各种应用程序和服务。 华为云服务器提供了多种实例类型,包括通用型、计算优化型、内存优化型等&#…...
Web自动化测试 —— 如何进行Selenium页面数据及元素交互?啊哈
前言: Web自动化测试是一种常用的测试方式,通过在浏览器中模拟用户操作以及与页面元素的交互,可以有效地检验页面的功能性以及稳定性。Selenium是一款流行的Web自动化测试工具,在本篇文章中,我们将介绍如何使用Seleni…...
点云从入门到精通技术详解100篇-基于全景图的室内场景点云补全方法(续)
目录 3.3 模型训练及实验评估 3.3.1 模型训练 3.3.2实验评估 4 基于自...
Debezium系列之:采集数据库数据实现对表指定的字段进行加密,下游实现对表加密后的字段进行解密
Debezium系列之:采集数据库数据实现对表指定的字段进行加密,下游实现对表加密后的字段进行解密 一、需求背景二、创建表三、深入理解加密算法的实现原理四、实现对表的指定字段加密五、插入数据六、消费Topic七、实现对加密的字段进行解密八、查看数据库一、需求背景 实际应用…...
Win10 cmd如何试用tar命令压缩和解压文件夹
环境: Win10 专业版 Microsoft Windows [版本 10.0.19041.208] 问题描述: Win10 cmd如何试用tar命令压缩和解压文件夹 C:\Users\Administrator>tar --help tar(bsdtar): manipulate archive files First option must be a mode specifier:-c Cre…...
最新AI写作系统ChatGPT源码/支持GPT4.0+GPT联网提问/支持ai绘画Midjourney+Prompt+MJ以图生图+思维导图生成
一、AI创作系统 SparkAi系统是基于很火的GPT提问进行开发的Ai智能问答系统。本期针对源码系统整体测试下来非常完美,可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI创作ChatGPT系统?小编这里写一个详细图文教程吧&#x…...
AI绘画普及课【二】图生图
文章目录 三、图生图1、图生图原理2、图生图的三个关键步骤3、参数技术性解析4、随机种子的含义研究 三、图生图 内容概要: 1、图生图原理 2、图生图基本流程 3、随机种子作用解析 1、图生图原理 图生图可以帮你把一张图片画成另一种模样。在文生图中我们看到&…...
C语言 数据类型
变量声明 格式(变量类型变量名称) 变量类型:整数类型(int),浮点数类型(float) float类型可以存储带小数的数字。 用printf()打印变量,使用%d来处理整数值,…...
瑞芯微RK3568:Debian系统如何安装Docker
本文基于HD-RK3568-IOT评估板演示Debian系统安装Docker,该方法适用于RK356X全系产品。 HD-RK3568-IOT评估板基于HD-RK3568-CORE 工业级核心板设计(双网口、双CAN、5路串口),接口丰富,适用于工业现场应用需求ÿ…...
联邦学习-Tensorflow实现联邦模型AlexNet on CIFAR-10
目录 Client端 Server端 扩展 Client.py Server.py Dataset.py Model.py 分享一种实现联邦学习的方法,它具有以下优点: 不需要读写文件来保存、切换Client模型 不需要在每次epoch重新初始化Client变量 内存占用尽可能小(参数量仅翻一…...
嵌入式Linux应用开发-文件 IO
嵌入式Linux应用开发-文件 IO 第四章 文件 IO4.1 文件从哪来?4.2 怎么访问文件?4.2.1 通用的 IO 模型:open/read/write/lseek/close4.2.2 不是通用的函数:ioctl/mmap 4.3 怎么知道这些函数的用法?4.4 系统调用函数怎么…...
【C++】多态,从使用到底层。
文章目录 前言一、多态的概念二、多太的定义和实现2.1 多太的构造条件2.2 虚函数2.3 重写(覆盖)2.4 C11 override 和 final2.5 重载,隐藏,重写 三、多态的原理3. 1虚函数表3.2 虚函数表如何完成多态的功能3.3 虚函数表存储在内存空间的那个区域ÿ…...
uvm白皮书练习_ch2_ch221只有driver的验证平台之*2.2.1 最简单的验证平台
uvm白皮书练习 ch221 dut.sv 这个DUT的功能非常简单,通过rxd接收数据,再通过txd发送出去。其中rx_dv是接收的数据有效指示,tx_en是发送的数据有效指示。 module dut (clk,rst_n,rxd,rx_dv,txd,tx_en );input clk ; input rst_n ; in…...
服务断路器_Resilience4j超时降级
创建模块cloud-consumer-resilience4j-order80 POM引入依赖 <dependencies><!-- 引入Eureka 客户端依赖 --><dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-netflix-eureka-client</a…...
【知识点随笔分析】我看看谁还不会用CURL命令
目录 前言: CURL介绍: CURL的基本使用: CURL与PING命令的区别: CURL命令的应用: 总结: 前言: 当今互联网时代,与服务器进行数据交互成为了无法回避的需求。无论是获取Web…...
ICCV 2023|Occ2Net,一种基于3D 占据估计的有效且稳健的带有遮挡区域的图像匹配方法...
本文为大家介绍一篇入选ICCV 2023的论文,《Occ2Net: Robust Image Matching Based on 3D Occupancy Estimation for Occluded Regions》, 一种基于3D 占据估计的有效且稳健的带有遮挡区域的图像匹配方法。 论文链接:https://arxiv.org/abs/23…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
多元隐函数 偏导公式
我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式,给定一个隐函数关系: F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 🧠 目标: 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z、 …...
