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

LeetCode 410. 分割数组的最大值

一、题目

1、题目描述

给定一个非负整数数组 nums 和一个整数 k ,你需要将这个数组分成 k 个非空的连续子数组。

设计一个算法使得这 k 个子数组各自和的最大值最小。

2、接口描述

class Solution {
public:int splitArray(vector<int>& nums, int k) {}
};

3、原题链接

410. Split Array Largest Sum


二、解题报告

1、思路分析

看到”最大的最小“自然想到二分

那么关键就在于给定x,如何判断原数组是否能够划分为最大值不超过x的k个子数组

我们贪心地思考,如果原数组能够划分为最大值不超过x的j个子数组,j < k,那么一定也可以通过拆解某些子数组从而得到k个子数组

所以我们的check函数,遍历数组,贪心累加,如果sum > x,我们就cnt + 1,然后sum = x

最终取决于cnt <= k

很经典的二分+贪心的题目

2、复杂度

时间复杂度:O(n) 空间复杂度:O(1)

3、代码详解

 
class Solution {
public:int splitArray(vector<int>& nums, int k) {int r = 0 , l = 0;for(auto x : nums) r += x , l = max(l , x);function<bool(int)> check = [&](int t){int cnt = 1 , s = 0;for(auto x : nums){if(s + x > t)s = x , cnt++;elses += x;}return cnt <= k;};while(l < r){int mid = (l + r) >> 1;if(check(mid)) r = mid;else l = mid + 1;}return r;}
};

相关文章:

LeetCode 410. 分割数组的最大值

一、题目 1、题目描述 给定一个非负整数数组 nums 和一个整数 k &#xff0c;你需要将这个数组分成 k 个非空的连续子数组。 设计一个算法使得这 k 个子数组各自和的最大值最小。 2、接口描述 ​ class Solution { public:int splitArray(vector<int>& nums, int …...

linux shell脚本 基础认识

Linux 系统中的 Shell 是一个特殊的应用程序&#xff0c;它介于操作系统内核与用户之间&#xff0c;充当 了一个“命令解释器”的角色&#xff0c;负责接收用户输入的操作指令&#xff08;命令&#xff09;并进行解释&#xff0c;将需要执行的操作传递给内核执行&#xff0c;并…...

一文(10图)了解Cornerstone3D核心概念(万字总结附导图)

Cornerstone3D介绍 Cornerstone3D是一个专门为处理三维医学影像而设计的JavaScript库。 它是Cornerstone项目的一部分&#xff0c;旨在为医学影像社区提供高性能、可扩展且易于使用的开源Web工具&#xff0c;专注于提供交互式的3D医学图像浏览体验&#xff0c;适用于多种医学…...

牛客网-----跳石头

题目描述&#xff1a; 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行&#xff0c;河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间&#xff0c;有N块岩石(不含起点和终点的岩石)。在比赛过程中&#xff0…...

用ChatGPT教学、科研!大学与OpenAI合作

亚利桑那州立大学&#xff08;简称“ASU”&#xff09;在官网宣布与OpenAI达成技术合作。从2024年2月份开始&#xff0c;为所有学生提供ChatGPT企业版访问权限&#xff0c;主要用于学习、课程作业和学术研究等。 为了帮助学生更好地学习ChatGPT和大语言模型产品&#xff0c;AS…...

运维平台介绍:视频智能运维平台的视频质量诊断分析和告警中心

目 录 一、视频智能运维平台介绍 &#xff08;一&#xff09;平台概述 &#xff08;二&#xff09;结构图 &#xff08;三&#xff09;功能介绍 1、运维监控 2、视频诊断 3、巡检管理 4、告警管理 5、资产管理 6、工单管理 7、运维…...

GAMES104-现代游戏引擎:从入门到实践 - 物理引擎课程笔记汇总

文章目录 0 入门资料1 物理引擎基本概念Actor & shapesRigid body dynamicsCollision DetectionCollision Resolution 应用与实践Character controllerRagdoll 0 入门资料 GAMES104-现代游戏引擎&#xff1a;从入门到实践_课程视频_bilibiliGAMES104官方账号 - 知乎课程主页…...

【linux】Xorg的工作原理

介绍 在linux系统上执行nvidia-smi时&#xff0c;总有一个进程占用gpu。 1 N/A N/A 2174 G /usr/lib/xorg/Xorg 4MiB /usr/lib/xorg/Xorg 是与X Window System&#xff08;简称X11或X&#xff09;相关的一个应用程序。X Window System是一个…...

02-docker下部署seata

官方部署文档 http://seata.io/zh-cn/docs/ops/deploy-by-docker 配置参数说明 http://seata.io/zh-cn/docs/user/configurations 1、镜像拉取 docker pull seata-server2、复制配置文件 mkdir /home/server/seata cd /home/server/seata docker run -d -p 8091:8091 -p 709…...

回归预测 | Matlab实现GA-APSO-MBP、GA-MBP、MBP、BP多输入单输出回归预测

回归预测 | Matlab实现GA-APSO-MBP、GA-MBP、MBP、BP多输入单输出回归预测 目录 回归预测 | Matlab实现GA-APSO-MBP、GA-MBP、MBP、BP多输入单输出回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab实现GA-APSO-MBP、GA-MBP、MBP、BP多输入单输出回归预测&…...

精益生产咨询背后的秘密:企业如何实现价值最大化

精益生产&#xff0c;起源于丰田生产系统&#xff0c;是一种集中于削减浪费、优化流程、提升顾客价值的生产方法。它的核心在于确保每一步生产过程都能为顾客创造价值。以下是实现精益生产咨询的详细步骤&#xff1a; 1.确定客户价值 一切从顾客需求出发。企业需深入理解顾客…...

创建SERVLET

创建SERVLET 要创建servlet,需要执行以下任务: 编写servlet。编译并封装servlet。将servlet部署为Java EE应用程序。通过浏览器访问servlet。编写servlet 要编写servlet,需要扩展HttpServlet接口的类。编写servlet是,需要合并读取客户机请求和返回响应的功能。 读取和处…...

python算法与数据结构(搜索算法和拓扑排序算法)---深度优先搜索

课程目标 了解树/图的深度遍历&#xff0c;宽度遍历基本原理&#xff1b;会使用python语言编写深度遍历&#xff0c;广度遍历代码&#xff1b;掌握拓扑排序算法 搜索算法的意义和作用 搜索引擎 提到搜索两个子&#xff0c;大家都应该会想到搜索引擎&#xff0c;搜索引擎的基…...

thinkphp5实战之phpstudy v8环境搭建,解决Not Found找不到路径问题

引言 thinkphp以快速、简约的大道至简的思想广受欢迎&#xff0c;适合开发小型项目。本地环境下&#xff0c;phpstudy v8是一款比较优秀的集成环境软件。部署完项目后&#xff0c;访问的时候傻眼&#xff0c;报错。 解决方案 不要慌&#xff0c;这个是伪静态的原因。选择apach…...

fastjson-BCEL不出网打法原理分析

FastJson反序列化漏洞 与原生的 Java 反序列化的区别在于&#xff0c;FastJson 反序列化并未使用 readObject 方法&#xff0c;而是由 FastJson 自定一套反序列化的过程。通过在反序列化的过程中自动调用类属性的 setter 方法和 getter 方法&#xff0c;将JSON 字符串还原成对…...

部署mysql主从同步,部署mysql数据读写分离结构+mycat2

主要命令 [rootmysql59 ~]# yum –y install mysql-server mysql[rootmysql59 ~]# systemctl start mysqld[rootmysql59 ~]# vim /etc/my.cnf.d/mysql-server.cnf[mysqld]server-id59log-binmysql59:wq[rootmysql59 ~]# systemctl restart mysqld//用户授权[rootmysql59 ~]# my…...

【最新!超详细C++入门】

01_C语言基础 一、课程目标 1、掌握 C基本语法&#xff1a;变量、常量、注释、标识符命名规范 2、掌握C数据类型 3、掌握C的输入和输出 4、掌握C运算符和表达式 5、掌握条件语句 6、掌握循环语句 二、课程内容 1 C初识 1.1 第一个C程序 编写一个C程序总共分为4个步骤…...

【Linux】【实战系列】10 分钟掌握日常开发中 Linux 网络处理相关命令

文章目录 lsofnetstatpingnslookupsshssh-keygenscpsftp 网络工具 curl网络工具 wget最后个人简介 hello&#xff0c;大家好&#xff0c;我是 Lorin&#xff0c;上一期和大家分享一期日常开发中常用的 Linux 文件和文本命令实战教学&#xff0c;这一期给大家带来常用的网络处理…...

语义分割常用评价指标

在图像处理领域中&#xff0c;语义分割是很重要的一个任务。在实际项目开发中,评估模型预测效果以及各指标的含义对于优化模型极为重要。 本文将主要评价指标的计算算法进行了详细说明,并加上注释解释每个指标的含义。这对理解各指标背后的数学原理以及能否在实践中应用或许有…...

从0开始学习C++ 第一课:你的第一个C++程序

第一课&#xff1a;你的第一个C程序 当然可以。让我们从C的基础开始&#xff0c;我们的第一课将覆盖以下几个主题&#xff1a; 程序结构编写和运行你的第一个C程序基本的输入输出&#xff08;I/O&#xff09; 第一课&#xff1a;你的第一个C程序 在C中&#xff0c;所有的程…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

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

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

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...