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

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...