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

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

相关文章

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 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python使用Pandas对比两列数据取最大值的五种方法

《Python使用Pandas对比两列数据取最大值的五种方法》本文主要介绍使用Pandas对比两列数据取最大值的五种方法,包括使用max方法、apply方法结合lambda函数、函数、clip方法、w... 目录引言一、使用max方法二、使用apply方法结合lambda函数三、使用np.maximum函数