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

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_elementmax_element函数找到数组nums中的最小值和最大值,分别存储在minmax中。

然后,在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 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统&#xff0c;所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。…...

正点原子lwIP学习笔记——Socket接口TCP实验

1. Socket接口TCP Client配置连接 配置步骤如下所示&#xff1a; sin_family设置为AF_INET表示IPv4网络协议&#xff1b;sin_port为设置端口号&#xff1b;sin_addr. s_addr设置远程IP地址&#xff1b;调用函数Socket创建Socket连接&#xff0c; 注意该函数的第二个参数SOCK_…...

【Flink】

事件驱动型应用 核心目标&#xff1a;数据流上的有状态计算 Apache Flink是一个框架和分布式处理引擎&#xff0c;用于对无界或有界数据流进行有状态计算。 运行逻辑 状态 把流处理需要的额外数据保存成一个“状态”,然后针对这条数据进行处理,并且更新状态。这就是所谓的“…...

大数据Flink(九十一):Array Expansion(数组列转行)和Table Function(自定义列转行)

文章目录 Array Expansion(数组列转行)和Table Function(自定义列转行)...

华为云云耀云服务器L实例评测|华为云云耀云服务器L实例CentOS的存储和备份策略

1 华为云云耀云服务器L实例介绍 华为云云耀云服务器L实例是华为云计算服务中的一种虚拟云服务器&#xff0c;它提供了强大的计算资源&#xff0c;可以在云端运行各种应用程序和服务。 华为云服务器提供了多种实例类型&#xff0c;包括通用型、计算优化型、内存优化型等&#…...

Web自动化测试 —— 如何进行Selenium页面数据及元素交互?啊哈

前言&#xff1a; Web自动化测试是一种常用的测试方式&#xff0c;通过在浏览器中模拟用户操作以及与页面元素的交互&#xff0c;可以有效地检验页面的功能性以及稳定性。Selenium是一款流行的Web自动化测试工具&#xff0c;在本篇文章中&#xff0c;我们将介绍如何使用Seleni…...

点云从入门到精通技术详解100篇-基于全景图的室内场景点云补全方法(续)

目录 3.3 模型训练及实验评估 3.3.1 模型训练 3.3.2实验评估 4 基于自...

Debezium系列之:采集数据库数据实现对表指定的字段进行加密,下游实现对表加密后的字段进行解密

Debezium系列之:采集数据库数据实现对表指定的字段进行加密,下游实现对表加密后的字段进行解密 一、需求背景二、创建表三、深入理解加密算法的实现原理四、实现对表的指定字段加密五、插入数据六、消费Topic七、实现对加密的字段进行解密八、查看数据库一、需求背景 实际应用…...

Win10 cmd如何试用tar命令压缩和解压文件夹

环境&#xff1a; Win10 专业版 Microsoft Windows [版本 10.0.19041.208] 问题描述&#xff1a; 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智能问答系统。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI创作ChatGPT系统&#xff1f;小编这里写一个详细图文教程吧&#x…...

AI绘画普及课【二】图生图

文章目录 三、图生图1、图生图原理2、图生图的三个关键步骤3、参数技术性解析4、随机种子的含义研究 三、图生图 内容概要&#xff1a; 1、图生图原理 2、图生图基本流程 3、随机种子作用解析 1、图生图原理 图生图可以帮你把一张图片画成另一种模样。在文生图中我们看到&…...

C语言 数据类型

变量声明 格式&#xff08;变量类型变量名称&#xff09; 变量类型&#xff1a;整数类型&#xff08;int&#xff09;&#xff0c;浮点数类型&#xff08;float&#xff09; float类型可以存储带小数的数字。 用printf()打印变量&#xff0c;使用%d来处理整数值&#xff0c…...

瑞芯微RK3568:Debian系统如何安装Docker

本文基于HD-RK3568-IOT评估板演示Debian系统安装Docker&#xff0c;该方法适用于RK356X全系产品。 HD-RK3568-IOT评估板基于HD-RK3568-CORE 工业级核心板设计&#xff08;双网口、双CAN、5路串口&#xff09;&#xff0c;接口丰富&#xff0c;适用于工业现场应用需求&#xff…...

联邦学习-Tensorflow实现联邦模型AlexNet on CIFAR-10

目录 Client端 Server端 扩展 Client.py Server.py Dataset.py Model.py 分享一种实现联邦学习的方法&#xff0c;它具有以下优点&#xff1a; 不需要读写文件来保存、切换Client模型 不需要在每次epoch重新初始化Client变量 内存占用尽可能小&#xff08;参数量仅翻一…...

嵌入式Linux应用开发-文件 IO

嵌入式Linux应用开发-文件 IO 第四章 文件 IO4.1 文件从哪来&#xff1f;4.2 怎么访问文件&#xff1f;4.2.1 通用的 IO 模型&#xff1a;open/read/write/lseek/close4.2.2 不是通用的函数&#xff1a;ioctl/mmap 4.3 怎么知道这些函数的用法&#xff1f;4.4 系统调用函数怎么…...

【C++】多态,从使用到底层。

文章目录 前言一、多态的概念二、多太的定义和实现2.1 多太的构造条件2.2 虚函数2.3 重写(覆盖)2.4 C11 override 和 final2.5 重载&#xff0c;隐藏&#xff0c;重写 三、多态的原理3. 1虚函数表3.2 虚函数表如何完成多态的功能3.3 虚函数表存储在内存空间的那个区域&#xff…...

uvm白皮书练习_ch2_ch221只有driver的验证平台之*2.2.1 最简单的验证平台

uvm白皮书练习 ch221 dut.sv 这个DUT的功能非常简单&#xff0c;通过rxd接收数据&#xff0c;再通过txd发送出去。其中rx_dv是接收的数据有效指示&#xff0c;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命令

目录 前言&#xff1a; CURL介绍&#xff1a; CURL的基本使用&#xff1a; CURL与PING命令的区别&#xff1a; CURL命令的应用&#xff1a; 总结&#xff1a; 前言&#xff1a; 当今互联网时代&#xff0c;与服务器进行数据交互成为了无法回避的需求。无论是获取Web…...

ICCV 2023|Occ2Net,一种基于3D 占据估计的有效且稳健的带有遮挡区域的图像匹配方法...

本文为大家介绍一篇入选ICCV 2023的论文&#xff0c;《Occ2Net: Robust Image Matching Based on 3D Occupancy Estimation for Occluded Regions》&#xff0c; 一种基于3D 占据估计的有效且稳健的带有遮挡区域的图像匹配方法。 论文链接&#xff1a;https://arxiv.org/abs/23…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...