想要精通算法和SQL的成长之路 - 分割数组的最大值
想要精通算法和SQL的成长之路 - 分割数组的最大值
- 前言
- 一. 分割数组的最大值
- 1.1 二分法
前言
想要精通算法和SQL的成长之路 - 系列导航
一. 分割数组的最大值
原题链接
首先面对这个题目,我们可以捕获几个关键词:
- 非负整数。
- 非空连续子数组。
那么我们假设分割后的子数组,和的最大值是M
,对应分割的子数组个数为N
。他们之间必然存在以下关系:
- 分割的子数组个数
N
越多,对应的和最大值M
也就越小。 - 分割的子数组个数
N
越少,对应的和最大值M
也就越大。
那么我们以每组和的最大值作为切入点,案例如下:
- 设置 数组各自和的最大值 为 20,此时分割依然是
[7, 2, 5, | 10, 8]
,此时分割的数组数为2。 - 设置 数组各自和的最大值 为 19,此时分割依然是
[7, 2, 5, | 10, 8]
,此时分割的数组数为2。 - 设置 数组各自和的最大值 为 18,此时分割依然是
[7, 2, 5, | 10, 8]
,此时分割的数组数为2。 - 设置 数组各自和的最大值 为 17,此时分割就变成了
[7, 2, 5, | 10, | 8]
,此时分割的数组数为3。
而我们题目要求分割组数是2,那么满足这个条件的几种情况,我们再取最大和最小的情况,最终得到结果是18。
1.1 二分法
二分的目标对象是什么?我们可以二分:数组各自和的最大值。那么二分法,就应该有初始区间:
left
:可以是当前数组的最大元素值。(单个元素一组)right
:可以是当前数组的总和。(所有元素成一组)
那么我们二分后取得 mid
:
int mid = left + (right - left) / 2;
接下来我们就要对数组进行分组计算了,对数组从左往右按顺序分组,使得分组后的各个子数组和不能超过mid
。我们可以编写个helper
函数:
public int helper(int[] nums, int maxGroupSum) {// 分组数最小是1int res = 1;int curSum = 0;for (int num : nums) {// 如果加入当前元素会导致和超过限制,那么就另外再分一组if (curSum + num > maxGroupSum) {res++;curSum = 0;}curSum += num;}return res;
}
我们计算好分组后的个数groupNum
之后,就需要和题目传入的k
进行对比:
groupNum > k
: 说明数组各自和的最大值还是小了,我们应该调大数组各自和的最大值。即left = mid +1
。- 反之:
right = mid;
最终代码如下:
public int splitArray(int[] nums, int k) {int max = 0, sum = 0;for (int num : nums) {max = Math.max(max, num);sum += num;}int left = max, right = sum;while (left < right) {int mid = left + (right - left) / 2;// 如果分组数比 k 还要大,说明每个分组的和最大值还是小了int groupNum = helper(nums, mid);if (groupNum > k) {left = mid + 1;} else {right = mid;}}return left;
}public int helper(int[] nums, int maxGroupSum) {// 分组数最小是1int res = 1;int curSum = 0;for (int num : nums) {// 如果加入当前元素会导致和超过限制,那么就另外再分一组if (curSum + num > maxGroupSum) {res++;curSum = 0;}curSum += num;}return res;
}
相关文章:

想要精通算法和SQL的成长之路 - 分割数组的最大值
想要精通算法和SQL的成长之路 - 分割数组的最大值 前言一. 分割数组的最大值1.1 二分法 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 分割数组的最大值 原题链接 首先面对这个题目,我们可以捕获几个关键词: 非负整数。非空连续子数组。 那么我…...

【深度学习】【Opencv】【GPU】python/C++调用onnx模型【基础】
【深度学习】【Opencv】【GPU】python/C调用onnx模型【基础】 提示:博主取舍了很多大佬的博文并亲测有效,分享笔记邀大家共同学习讨论 文章目录 【深度学习】【Opencv】【GPU】python/C调用onnx模型【基础】前言Python版本OpenCVWindows平台安装OpenCVopencv调用onnx模型 C版本…...

Oracle update 关联更新优化方法
关联更新顾名思义就是指,更新的数据从关联的表中获取并update到目标表。并且该SQL将会是一个天然的嵌套循环。有两种优化思路解决: 1、PLSQL 根据rowid更新 是否需要加order by rowid的考量: 如果buffer cache足够大,能够放得下要…...
USB协议学习(一)帧格式以及协议抓取
USB协议学习(一)帧格式以及协议抓取 笔者来聊聊MPU的理解 这里写自定义目录标题 USB协议学习(一)帧格式以及协议抓取MPU的概念以及作用MPU的配置新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式…...
前端工程化知识系列(8)
目录 71.你有经验使用TypeScript或Flow等类型检查工具来提高前端代码的可维护性和质量吗?72. 如何处理前端应用的搜索引擎优化(SEO)问题,特别是在单页面应用(SPA)中?73. 你了解渐进式Web应用&am…...

UnrealEngine iOS 打包 —— 签名证书(cer、p12)生成
官方文档 docs.unrealengine.com/5.3/zh-CN/setting-up-ios-tvos-and-ipados-provisioning-profiles-and-signing-certificates-for-unreal-engine-projects 打开 ProjectSettings -> Platforms -> iOS 可以看到签名证书配置 需要拓展名为 .cer 和 .p12 的一对证书和密钥…...

【广州华锐互动】VR高层火灾应急疏散演练提供一种无风险的逃生体验
在科技进步的今天,我们已经能够利用虚拟现实(VR)技术来模拟各种紧急情况,其中就包括高楼火灾逃生。VR高层火灾应急疏散演练系统是一种新兴的技术,它使用虚拟现实环境来模拟高楼火灾的实际情况,为人们提供一…...
定档通知2024中国(上海)国际品牌叉车展览会
时 间:2024年7月24~26日 地 点:上海国家会展中心 ◆ 》》》展会概况: 叉车在“搬运设备”中扮演着非常重要的角色,是机械化装卸、堆垛和短距离运输的高效设备。近年来,在“节能环保,…...

Ubuntu编译安装colmap遇到的几个问题以及解决
总体安装过程已经很明白了,写的人很多了,我就不赘述了,可以参考这里或者其他博客。我主要记录几个我遇到的问题以及解决方法。 1、cmake报错:No CMAKE_CUDA_COMPILER could be found. 这个原因是没找到cuda和nvcc目录࿰…...

【Qt上位机】打开本地表格文件并获取其中全部数据
前言 其实本文所实现的功能并非博主要实现的全部功能,只是全部功能中的一小部分,这里只是为了记录一下实现方法,防止后续忘记,仅供参考。 文章目录 一、实现效果二、UI设计三、程序设计3.1 选择本地表格文件3.2 获取表格总行列数3…...

香港服务器选纯国际线路上网稳定吗?
关于香港服务器的线路,我们平时接触较多的分三大类,即纯国际线路、回国专线和香港本地线路。三者价格上存有差距,原因体现在线路和网络质量上,当然这些会关系到服务器的速度和稳定性。譬如,有些用户在选择了纯国…...

USB PD3.1
目前我们大多数Type-C接口仍然采用的是PD3.0快充协议,按当前用户的使用场景来看功率也完全够用,那么PD3.1快充协议是什么?USB PD3.1到底有没有必要? 不妨我们先了解一下PD3.1: 5月25日,USB-IF协会推出了USB Type-C线…...
unity面试八股文 - 基础篇
委托是什么? event 关键字有什么用? 委托: 委托是一种特殊类型的对象,它包含了对一个方法的引用。简单来说,委托就像是一个安全的函数指针。它允许我们创建可在运行时动态更改其引用方法的变量,并且可以指向类中定义…...

构建高效问题解答平台:使用Cpolar和Tipas在Ubuntu上搭建专属问答网站
文章目录 前言2.Tipask网站搭建2.1 Tipask网站下载和安装2.2 Tipask网页测试2.3 cpolar的安装和注册 3. 本地网页发布3.1 Cpolar临时数据隧道3.2 Cpolar稳定隧道(云端设置)3.3 Cpolar稳定隧道(本地设置) 4. 公网访问测试5. 结语 前…...

前馈型BP神经网络
1.感知机和激活函数 感知机,是构成神经网络的基本单位,一个感知机可以接收n个输入X(x1,x2,x3…xn)T(每个输入,可以理解为一种特征),n个输入对应n个权值W(w1,w2,w3…wn),此外还有一个偏置项b&am…...

数据库实验一:学生信息管理系统数据库结构搭建和表的创建
实验项目名称:学生信息管理系统数据库结构搭建和表的创建 实验目的与要求实验原理与内容1. 数据库的组织结构2. 数据库的分离和附加3. 数据库表的创建,修改和删除 实验过程与结果1. 根据学生信息管理系统创建相关的数据库2. 数据库表初步设计及实现3. 实…...

解决 vscode使用Prettier格式化js文件报错:Cannot find module ‘./parser-babylon‘
报错如下: ["ERROR" - 11:48:58] Error formatting document. ["ERROR" - 11:48:58] Cannot find module ./parser-babylon Require stack: - d:\VueCode\VueProject\myqqmusic\node_modules\prettier\index.js - c:\Users\Administrator.SKY-2…...

汉服商城小程序的作用是什么
汉服在日常生活中越来越常见,大街小巷也有不少年轻人装扮甚是漂亮帅气,有些地区甚至还有相关的比赛等,作为近几年曝光的服饰,汉服市场规模持续增加中,各地线上线下商家也多了起来。 然而在实际经营中,汉服…...

9月大型语言模型研究论文总结
大型语言模型(llm)在今年发展迅速,随着新一代模型不断地被开发,研究人员和工程师了解最新进展变得非常重要。本文总结9-10月期间发布了一些重要的LLM论文。 这些论文涵盖了一系列语言模型的主题,从模型优化和缩放到推理、基准测试和增强性能…...

微信小程序--小程序框架
目录 前言: 一.框架基本介绍 1.整体结构: 2.页面结构: 3.生命周期: 4.事件系统: 5.数据绑定: 6.组件系统: 7.API: 8.路由: 9.模块化: 10.全局配置&…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...