想要精通算法和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.全局配置&…...

Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...