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

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

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系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;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语音助手,涵盖基础功…...