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

【C++二分查找】2560. 打家劫舍 IV

本文涉及的基础知识点

C++二分查找

LeetCode2560. 打家劫舍 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 。
    提示:
    1 <= nums.length <= 105
    1 <= nums[i] <= 109
    1 <= k <= (nums.length + 1)/2

二分查找

性质一:如果存在某种方案窃取能力为x,则一定存在盗取了k间房屋的方案窃取能力为x。方案变换规则:删除现金少的房屋,直到房间数为k。
Check函数: 是否存在方案,窃取能力小于等于mid。
cnt[0]记录没有窃取nums[i-1]盗窃房屋的数量,cnt[1]记录盗窃了nums[i-1]房屋的数量。
return max(cnt[0],ctn[1]) >= k。
二分方式:寻找首端
Check函数的参数范围:[1,1e9]

代码

核心代码

template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:int minCapability(vector<int>& nums, int k) {auto Check = [&](int mid) {int cnt[2] = { 0 };for (const auto& n: nums) {auto tmp = max(cnt[0], cnt[1]);if (n <= mid) {cnt[1] = cnt[0] + 1;}else {cnt[1] = 0;}cnt[0] = tmp;}return max(cnt[0], cnt[1]) >= k;};return CBinarySearch<int>(1, 1e9).FindFrist(Check);}};

单元测试

vector<int> nums;int k;TEST_METHOD(TestMethod1){nums = { 1 }, k = 1;auto res = Solution().minCapability(nums, k);AssertEx(1, res);}TEST_METHOD(TestMethod2){nums = { 1000'000'000 }, k = 1;auto res = Solution().minCapability(nums, k);AssertEx(nums[0], res);}TEST_METHOD(TestMethod11){nums = { 2,3,5,9 },k=2;auto res = Solution().minCapability(nums,k);AssertEx(5, res);}TEST_METHOD(TestMethod12){nums = { 2,7,9,3,1 },k=2;auto res = Solution().minCapability(nums,k);AssertEx(2, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:

【C++二分查找】2560. 打家劫舍 IV

本文涉及的基础知识点 C二分查找 LeetCode2560. 打家劫舍 IV 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统&#xff0c;所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在…...

位段、枚举、联合

位段 在一个结构体中以位&#xff08;最小单位&#xff09;为单位来指定其成员所占的内存长度。位段成员名后面有一个冒号&#xff0c;冒号后有一个数字&#xff08;这个数字是小于等于这个成员所占的位&#xff09;。 typedef struct S {char a : 2;//8char b : 8;//8char c …...

golang学习笔记15——golang依赖管理方法

推荐学习文档 golang应用级os框架&#xff0c;欢迎star基于golang开发的一款超有个性的旅游计划app经历golang实战大纲golang优秀开发常用开源库汇总golang学习笔记01——基本数据类型golang学习笔记02——gin框架及基本原理golang学习笔记03——gin框架的核心数据结构golang学…...

Linux 挂载磁盘与开机自动挂载操作指南

Linux 挂载磁盘与开机自动挂载操作指南 文章目录 Linux 挂载磁盘与开机自动挂载操作指南一 挂载磁盘1 查看硬盘信息2 新增数据盘执行分区3 新建分区4 创建一个主分区5 分区编号6 初始磁柱编号7 截止磁柱编号8 查看新建分区信息9 分区结果写入10 新分区同步操作系统11 设置新分区…...

『功能项目』单例模式框架【37】

我们打开上一篇36C#拓展 - 优化冗余脚本的项目&#xff0c; 本章要做的事情是编写单例模式基类&#xff0c;让继承其基类的子类在运行时只存在一个&#xff0c;共有两个单例基类框架&#xff0c;分别是不继承MonoBehaviour的单例和继承MonoBehaviour的单例框架 首先编写不继承…...

【计算机网络 - 基础问题】每日 3 题(三)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏&…...

SpringCloud Nacos

**************************** 准备工作 首先准备号nacos的镜像 根据镜像创建nacos容器 nacos:container_name: nacosimage: nacos/nacos-server:v2.1.0-slimports: #需要监听三个端口- "8848:8848"- "9848:9848"- "9849:9849"privileged: tr…...

机器学习算法详细解读和python实现

文章目录 一、机器学习概述1.1 机器学习的定义与分类机器学习的分类 1.2 机器学习的基本流程1.3 Python在机器学习中的应用Python的优势Python在机器学习中的应用场景 2.1 线性回归的基本概念线性回归的数学表达线性回归的目标 2.2 最小二乘法技术最小二乘法的数学推导最小二乘…...

【Linux】Linux权限历险记---组和用户的关系

欢迎来到 CILMY23 的博客 &#x1f3c6;本篇主题为&#xff1a;Linux权限历险记---组和用户的关系 &#x1f3c6;个人主页&#xff1a;CILMY23-CSDN博客 &#x1f3c6;系列专栏&#xff1a;Python | C | C语言 | 数据结构与算法 | 贪心算法 | Linux | 算法专题 | 代码训练营…...

华为HCIA、HCIP和HCIE认证考试明细

华为认证体系包括三个主要等级&#xff1a;HCIA&#xff08;华为认证ICT助理&#xff09;、HCIP&#xff08;华为认证ICT高级工程师&#xff09;和HCIE&#xff08;华为认证ICT专家&#xff09;。每个等级的认证都有其特定的考试内容和费用。 HCIA&#xff08;华为认证ICT助理…...

C++数据结构

单向链表 // // Created by 19342 on 2024/9/14. // #include <iostream> using namespace std;// 定义链表节点 struct Node {int data; // 节点存储的数据Node* next; // 指向下一个节点的指针 };// 初始化链表 Node* initList() {return nullptr; }// 在链表末尾添加…...

Linux下read函数详解

在Linux中&#xff0c;read 函数是最常用的系统调用之一&#xff0c;用于从文件或其他输入设备读取数据。它是低级别的I/O操作的核心&#xff0c;直接与操作系统的内核交互&#xff0c;提供了高效的数据读取方式。 一、read 函数简介 read 函数的声明如下&#xff1a; #inclu…...

【二叉树遍历算法应用】------补录

0.二叉树结点的链式存储结构 #include<stdio.h> #include<stdlib.h> #include<stdbool.h>typedef char TElemType;//树中元素基本类型为char类型//二叉树结点链式存储结构&#xff08;二叉链表&#xff09; typedef struct BiNode {TElemType data;//数据域…...

AtCoder Beginner Contest 368

A.Cut&#xff08;模拟&#xff09; 题意&#xff1a; 有一叠 N N N张扑克牌&#xff0c;最上面的 i i i张扑克牌上写着一个整数 A _ i A\_i A_i。 你从牌堆底部取出 K K K张牌&#xff0c;将它们放在牌堆顶部&#xff0c;并保持它们的顺序。 操作后从上到下输出写在卡…...

WebGL系列教程六(纹理映射与立方体贴图)

目录 1 前言2 思考题3 纹理映射介绍4 怎么映射&#xff1f;5 开始绘制5.1 声明顶点着色器和片元着色器5.2 修改顶点的颜色为纹理坐标5.3 指定顶点位置和纹理坐标的值5.4 获取图片成功后进行绘制5.5 效果5.6 完整代码 6 总结 1 前言 上一讲我们讲了如何使用索引绘制彩色立方体&a…...

为什么nii.gz转.nrrd标签体积变大?

import SimpleITK as sitk # nii nii.gz nrrd格式之间互相转换 def nii2nii(oripath, savepath):data sitk.ReadImage(oripath)img sitk.GetArrayFromImage(data)out sitk.GetImageFromArray(img)sitk.WriteImage(out, savepath)if __name__ __main__:oripath 00292625.ni…...

软件安装攻略:EmEditor编辑器下载安装与使用

EmEditor是一款在Windows平台上运行的文字编辑程序。EmEditor以运作轻巧、敏捷而又功能强大、丰富著称&#xff0c;得到许多用户的好评。Windows内建的记事本程式由于功能太过单薄&#xff0c;所以有不少用户直接以EmEditor取代&#xff0c;emeditor是一个跨平台的文本编辑器&a…...

Redis的watch机制详解

WATCH 是 Redis 提供的一个用于实现 乐观锁 (Optimistic Lock) 的命令&#xff0c;通常用于实现事务中的并发控制。它允许客户端监控一个或多个键的变化&#xff0c;并确保事务&#xff08;MULTI/EXEC&#xff09;中执行的操作在这些键没有发生改变的情况下才能成功提交。若在事…...

UnrealEngine 打包Android平台应用

虚幻引擎 支持将项目发布到 安卓&#xff08;Android&#xff09; 移动设备上&#xff0c;并且提供了若干功能帮你将项目发布到 谷歌游戏商店。本节包含了如何设置Android开发环境、如何使用Android功能和服务、以及如何为发布游戏做准备相关的指南。 当前SDK要求 当前UE版本…...

Linux:git

hello&#xff0c;各位小伙伴&#xff0c;本篇文章跟大家一起学习《Linux&#xff1a;git》&#xff0c;感谢大家对我上一篇的支持&#xff0c;如有什么问题&#xff0c;还请多多指教 &#xff01; 如果本篇文章对你有帮助&#xff0c;还请各位点点赞&#xff01;&#xff01;&…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

[特殊字符] 手撸 Redis 互斥锁那些坑

&#x1f4d6; 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作&#xff0c;想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁&#xff0c;也顺便跟 Redisson 的 RLock 机制对比了下&#xff0c;记录一波&#xff0c;别踩我踩过…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...

联邦学习带宽资源分配

带宽资源分配是指在网络中如何合理分配有限的带宽资源&#xff0c;以满足各个通信任务和用户的需求&#xff0c;尤其是在多用户共享带宽的情况下&#xff0c;如何确保各个设备或用户的通信需求得到高效且公平的满足。带宽是网络中的一个重要资源&#xff0c;通常指的是单位时间…...

GC1808:高性能音频ADC的卓越之选

在音频处理领域&#xff0c;高质量的音频模数转换器&#xff08;ADC&#xff09;是实现精准音频数字化的关键。GC1808&#xff0c;一款96kHz、24bit立体声音频ADC&#xff0c;以其卓越的性能和高性价比脱颖而出&#xff0c;成为众多音频设备制造商的理想选择。 GC1808集成了64倍…...