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

想要精通算法和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的成长之路 - 系列导航 一. 分割数组的最大值 原题链接 首先面对这个题目&#xff0c;我们可以捕获几个关键词&#xff1a; 非负整数。非空连续子数组。 那么我…...

【深度学习】【Opencv】【GPU】python/C++调用onnx模型【基础】

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

Oracle update 关联更新优化方法

关联更新顾名思义就是指&#xff0c;更新的数据从关联的表中获取并update到目标表。并且该SQL将会是一个天然的嵌套循环。有两种优化思路解决&#xff1a; 1、PLSQL 根据rowid更新 是否需要加order by rowid的考量&#xff1a; 如果buffer cache足够大&#xff0c;能够放得下要…...

USB协议学习(一)帧格式以及协议抓取

USB协议学习&#xff08;一&#xff09;帧格式以及协议抓取 笔者来聊聊MPU的理解 这里写自定义目录标题 USB协议学习&#xff08;一&#xff09;帧格式以及协议抓取MPU的概念以及作用MPU的配置新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式…...

前端工程化知识系列(8)

目录 71.你有经验使用TypeScript或Flow等类型检查工具来提高前端代码的可维护性和质量吗&#xff1f;72. 如何处理前端应用的搜索引擎优化&#xff08;SEO&#xff09;问题&#xff0c;特别是在单页面应用&#xff08;SPA&#xff09;中&#xff1f;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高层火灾应急疏散演练提供一种无风险的逃生体验

在科技进步的今天&#xff0c;我们已经能够利用虚拟现实&#xff08;VR&#xff09;技术来模拟各种紧急情况&#xff0c;其中就包括高楼火灾逃生。VR高层火灾应急疏散演练系统是一种新兴的技术&#xff0c;它使用虚拟现实环境来模拟高楼火灾的实际情况&#xff0c;为人们提供一…...

定档通知2024中国(上海)国际品牌叉车展览会

时 间&#xff1a;2024年7月24&#xff5e;26日 地 点&#xff1a;上海国家会展中心 ◆ 》》》展会概况&#xff1a; 叉车在“搬运设备”中扮演着非常重要的角色&#xff0c;是机械化装卸、堆垛和短距离运输的高效设备。近年来&#xff0c;在“节能环保&#xff0c…...

Ubuntu编译安装colmap遇到的几个问题以及解决

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

【Qt上位机】打开本地表格文件并获取其中全部数据

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

香港服务器选纯国际线路上网稳定吗?

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

USB PD3.1

目前我们大多数Type-C接口仍然采用的是PD3.0快充协议&#xff0c;按当前用户的使用场景来看功率也完全够用&#xff0c;那么PD3.1快充协议是什么&#xff1f;USB PD3.1到底有没有必要&#xff1f; 不妨我们先了解一下PD3.1: 5月25日&#xff0c;USB-IF协会推出了USB Type-C线…...

unity面试八股文 - 基础篇

委托是什么? event 关键字有什么用&#xff1f; 委托&#xff1a; 委托是一种特殊类型的对象&#xff0c;它包含了对一个方法的引用。简单来说&#xff0c;委托就像是一个安全的函数指针。它允许我们创建可在运行时动态更改其引用方法的变量&#xff0c;并且可以指向类中定义…...

构建高效问题解答平台:使用Cpolar和Tipas在Ubuntu上搭建专属问答网站

文章目录 前言2.Tipask网站搭建2.1 Tipask网站下载和安装2.2 Tipask网页测试2.3 cpolar的安装和注册 3. 本地网页发布3.1 Cpolar临时数据隧道3.2 Cpolar稳定隧道&#xff08;云端设置&#xff09;3.3 Cpolar稳定隧道&#xff08;本地设置&#xff09; 4. 公网访问测试5. 结语 前…...

前馈型BP神经网络

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

数据库实验一:学生信息管理系统数据库结构搭建和表的创建

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

解决 vscode使用Prettier格式化js文件报错:Cannot find module ‘./parser-babylon‘

报错如下&#xff1a; ["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…...

汉服商城小程序的作用是什么

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

9月大型语言模型研究论文总结

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

微信小程序--小程序框架

目录 前言&#xff1a; 一.框架基本介绍 1.整体结构&#xff1a; 2.页面结构&#xff1a; 3.生命周期&#xff1a; 4.事件系统&#xff1a; 5.数据绑定&#xff1a; 6.组件系统&#xff1a; 7.API&#xff1a; 8.路由&#xff1a; 9.模块化&#xff1a; 10.全局配置&…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...