算法每日一题: 分割数组的最大值 | 动归 | 分割数组 | 贪心+二分

2024-01-22 18:28

本文主要是介绍算法每日一题: 分割数组的最大值 | 动归 | 分割数组 | 贪心+二分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Hello,大家好,我是星恒
呜呜呜,今天给大家带来的又是一道经典的动归难题。

题目:leetcode 410
给定一个非负整数数组 nums 和一个整数 k ,你需要将这个数组分成 k_ 个非空的连续子数组。
设计一个算法使得这 k
_个子数组各自和的最大值最小。
示例:
示例 1:

输入:nums = [7,2,5,10,8], k = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。 
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。

示例 2:

输入:nums = [1,2,3,4,5], k = 2
输出:9

示例 3:

输入:nums = [1,4,4], k = 3
输出:4

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= k <= min(50, nums.length)

分析:
这次这道恐怖的困难题,就先和大家分享第一种动态规划的方法,第二种方法是二分 + 贪心,这里给大家附上答案,大家可以自行研究,后续有时间我会给大家补回来。

好,我来看如果使用动归来解这道题目:

这道题假设我们把它分为四段,我们可以枚举最后一段出现的位置k,然后来看是前面的情况的最大值大(前面的最大值通过递归来求,我们这里默认知道前面情况的最大值),还是最后一段的最大值大,从而得到这种k情况下的最大值。我们遍历k,看哪种情况的最大值最优(也就是最小)

那么前面情况的最大值如何求,其实步骤和上述一样。比如上述情况,我们需要前4点分成3段时的情况(也就是分成三段的最优情况),同理,再往前推我们需要知道分成两段的最优情况,这样,我们从开始一步一步推就可以了。

所以基本问题就变成了:求将i个数数分成j段的每种情况的最小最大数了

对于状态 f[i][j],由于我们不能分出空的子数组,因此合法的状态必须有 i≥j。对于不合法(i<j)的状态,由于我们的目标是求出最小值,因此可以将这些状态全部初始化为一个很大的数。在上述的状态转移方程中,一旦我们尝试从不合法的状态 f[k][j−1]进行转移,那么 max⁡(⋯ ) 将会是一个很大的数,就不会对最外层的 min⁡{⋯ }产生任何影响。

此外,我们还需要将 f[0][0]的值初始化为 0。在上述的状态转移方程中,当 j=1 时,唯一的可能性就是前 i个数被分成了一段。如果枚举的 k=0,那么就代表着这种情况;如果 k≠0,对应的状态f[k][0] 是一个不合法的状态,无法进行转移。因此我们需要令 f[0][0]=0。

总结:「将数组分割为 mmm 段,求……」是动态规划题目常见的问法。
遇到这种分段的,除了要求将每一种情况列出来,使用回溯枚举每一种情况,一般都是动归
这种题的规律是:枚举每一段元素可能出现的元素,可能被分割成每种段数的情况

– 动归:现在的某种状态好,还是从以前直接弄过来的状态好

题解:
题解1:动态规划

class Solution {public int splitArray(int[] nums, int m) {int n = nums.length;int[][] f = new int[n + 1][m + 1];for (int i = 0; i <= n; i++) {Arrays.fill(f[i], Integer.MAX_VALUE);}int[] sub = new int[n + 1];for (int i = 0; i < n; i++) {sub[i + 1] = sub[i] + nums[i];}f[0][0] = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= Math.min(i, m); j++) {for (int k = 0; k < i; k++) {f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k]));}}}return f[n][m];}
}

题解2:二分 + 贪心
「使……最大值尽可能小」是二分搜索题目常见的问法。

class Solution {public int splitArray(int[] nums, int m) {int left = 0, right = 0;for (int i = 0; i < nums.length; i++) {right += nums[i];if (left < nums[i]) {left = nums[i];}}while (left < right) {int mid = (right - left) / 2 + left;if (check(nums, mid, m)) {right = mid;} else {left = mid + 1;}}return left;}public boolean check(int[] nums, int x, int m) {int sum = 0;int cnt = 1;for (int i = 0; i < nums.length; i++) {if (sum + nums[i] > x) {cnt++;sum = nums[i];} else {sum += nums[i];}}return cnt <= m;}
}

如果大家有什么思考和问题,可以在评论区讨论,也可以私信我,很乐意为大家效劳。
好啦,今天的每日一题到这里就结束了,如果大家觉得有用,可以可以给我一个小小的赞呢,我们下期再见!

这篇关于算法每日一题: 分割数组的最大值 | 动归 | 分割数组 | 贪心+二分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/633845

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

Python如何将大TXT文件分割成4KB小文件

《Python如何将大TXT文件分割成4KB小文件》处理大文本文件是程序员经常遇到的挑战,特别是当我们需要把一个几百MB甚至几个GB的TXT文件分割成小块时,下面我们来聊聊如何用Python自动完成这... 目录为什么需要分割TXT文件基础版:按行分割进阶版:精确控制文件大小完美解决方案:支持UTF-8编码

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示