分割数组的两种解法:动态规划、二分法
1. 动态规划
「将数组分割为 m 段,求……」是动态规划题目常见的问法
理清状态转移方程比较难,因此不推荐用动态规划解题。
2. 贪心 + 二分法
「使……最大值尽可能小」是二分搜索题目常见的问法。
本题中,我们注意到:当我们选定一个值 x,我们可以线性地验证是否存在一种分割方案,满足其最大分割子数组和不超过 x。
贪心地模拟分割的过程,从前到后遍历数组,用 sum 表示当前分割子数组的和,cnt 表示已经分割出的子数组的数量(包括当前子数组),那么每当 sum 加上当前值超过了 cnt,我们就把当前取的值作为新的一段分割子数组的开头,并将 cnt 加 1。遍历结束后验证是否 cnt 不超过 k。
利用二分法搜索:
class Solution {
public:
int match(vector<int>& nums, int k, int minSum) {
int cnt{1};
int tmpSum{0};
for (int i = 0; i < nums.size(); ++i) {
if (tmpSum + nums[i] > minSum) {
cnt++;
tmpSum = nums[i]; // 重新累加
} else {
tmpSum += nums[i];
}
}
return cnt;
}
int splitArray(vector<int>& nums, int k) {
int ans{0};
int l = *max_element(nums.begin(), nums.end());
int r{0};
for (auto & num: nums) {
r += num;
}
int mid{0};
// 二分法搜索
while (l < r) {
mid = l + (r - l) / 2;
if (match(nums, k, mid) > k) {
l = mid + 1;
} else {
r = mid;
}
}
ans = l;
return ans;
}
};
原文地址:https://blog.csdn.net/csdnzzt/article/details/136771509
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!