当前位置: 首页 > 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…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

webpack面试题

面试题&#xff1a;webpack介绍和简单使用 一、webpack&#xff08;模块化打包工具&#xff09;1. webpack是把项目当作一个整体&#xff0c;通过给定的一个主文件&#xff0c;webpack将从这个主文件开始找到你项目当中的所有依赖文件&#xff0c;使用loaders来处理它们&#x…...