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

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

电脑桌面太单调,用Python写一个桌面小宠物应用。

下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡&#xff0c;可以响应鼠标点击&#xff0c;并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...

ZYNQ学习记录FPGA(二)Verilog语言

一、Verilog简介 1.1 HDL&#xff08;Hardware Description language&#xff09; 在解释HDL之前&#xff0c;先来了解一下数字系统设计的流程&#xff1a;逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端&#xff0c;在这个过程中就需要用到HDL&#xff0c;正文…...