贪心-LeetCode410. 分割数组的最大值
程序员文章站
2022-05-31 10:57:56
1、题目描述https://leetcode-cn.com/problems/split-array-largest-sum/给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意: 数组长度 n 满足以下条件: 1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n)输入: nums = [7,2,5,10,8] m = 2 输出: 18 解释: 一共有四种方法将nums分割为2个子数组。.....
1、题目描述
https://leetcode-cn.com/problems/split-array-largest-sum/
给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意: 数组长度 n 满足以下条件: 1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n)
输入: nums = [7,2,5,10,8] m = 2
输出: 18
解释: 一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8], 因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
2、代码详解
为什么要贪心地使子数组和不断逼近mid?
- 我先猜一个mid值,然后遍历数组划分,使每个子数组和都最接近mid(贪心地逼近mid),这样我得到的子数组数一定最少;
- 如果即使这样子数组数量仍旧多于m个,那么明显说明我mid猜小了,因此 lo = mid + 1;
- 而如果得到的子数组数量小于等于m个,那么我可能会想,mid是不是有可能更小?值得一试。因此 hi = mid;
class Solution(object):
def splitArray(self, nums, m):
# 由于题目的返回要求:返回最小和的值
# 最小和必然在 [max(nums), sum(nums)] 间
# 可以使用二分来进行查找
low, high = max(nums), sum(nums)
while low < high:
mid = (low + high) // 2
# 淘汰算法
# 数组分成 m 个非空的连续子数组
# 由前向后对nums进行划分,使其子数组和 <= mid,然后统计满足条件的数组数量
# 若我们选的sum值过小,则满足条件的数量 > m,目标值应落在 [mid+1, high]
# 若我们选的sum值过大,则满足条件的数量 < m,目标值应落在 [low, mid-1]
count = 0
sub_sum = 0
for i in range(len(nums)):
sub_sum += nums[i]
if sub_sum > mid:
count += 1
sub_sum = nums[i]
# 注意:末尾还有一个子数组我们没有统计,这里把它加上
count += 1
if count > m:
low = mid + 1
else:
high = mid
return low
nums = [7, 2, 5, 10, 8]
# # 分为[7,2,5] [10,8], 此时这两个子数组各自的和的最大值为18,在所有情况中最小。
m = 2
s = Solution()
print(s.splitArray(nums, m))
本文地址:https://blog.csdn.net/IOT_victor/article/details/107581397
推荐阅读
-
JS实现textarea通过换行或者回车把多行数字分割成数组并且去掉数组中空的值
-
贪心-LeetCode410. 分割数组的最大值
-
asp实现取得数组中的最大值的代码
-
Java实现求子数组和的最大值算法示例
-
php将字符串随机分割成不同长度数组的方法
-
求PHP数组最大值,最小值的代码
-
SQL Server 2008 R2——查找最小nIndex,nIndex存在而nIndex+1不存在 求最小连续数组中的最大值
-
支持中文的PHP按字符串长度分割成数组代码
-
[Leetcode][第410题][JAVA][分割数组的最大值][动态规划][二分]
-
解决java 分割字符串成数组时,小圆点不能直接进行分割的问题