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

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...